RBFS is a simple recursive algo that attempt to mimic the operation of standard BFS, but using only linear space. The algo is shown in figure 4.5. Its structure is similar to that of recursive DFS, but rather than continuing indefinitely down the current path, it keeps track of the F – Value of the best alternative path available from any ancestor of the current node. If the current node exceeds this limit, the recursion unwinds back to the alternative path. As the recursion unwinds, RBFS replaces the F-Value of each node along the path with the best F-Value of its children.

In this way, RBFS remembers the F-Value of the best leaf in the forgotten sub-tree and can therefore decide whether it’s worth re expanding the sub-tree at some later time. Figure 4.6 shows how RBFS reaches Bucharest.

function RECURSIVE – BEST – FIRST – SEARCH (Problem) return

RBFS (Problem, MAKE – NODE) (INITIAL – STATE [problem

function RBFS (problem, node, f - limit) return a solution, failure and

a new f – cost limit

if GOAL – TEST [problem] (state) then return node

successors $\leftarrow$ EXPAND (node, problem)

if successors is empty then return failure, $\infty$

for each g in successors do