title: Recursive best first search and finding the best path
body: <p>In a Recursive Best-First Search, how would I modify it, to be able to track back the route? </p>
  
  <p>Would I need to have a data structure that keeps track of which nodes are unwound after last recursion break?</p>
  
  <p>I already have implemented heuristic and helper functions (graph parser, distance calculations) in LISP and RBFS itself as well. Now, in order to print the most optimal path, I  have a list of all return values (result) from each recursion step.</p>
  
  <p>See <a href="http://mas.cs.umass.edu/classes/cs683/lectures-2010/Lec6_Search5-F2010.pdf" rel="nofollow noreferrer">RBFS - Recursive Best-First Search Algorithm (PDF, slide 4)</a>.</p>
  
  <p>My LISP code:</p>
  
  <pre><code>(defun rbfs (state cost f-limit goal)
    (let ((node (first state))
          (f (second state)))
      (if (equal node goal)
          (list node cost)
          (let ((successors
                 (loop
                     :for city :in (expand node)
                     :collect (list city (max (+ cost (getdistance city node)
                                                 (getlineardistance city goal)) f))
                     :into successors
                     :finally (sort successors #'my-comparator)))
                (result (list)))
            (if (&lt; (length successors) 2)
                (list fail inf)
                (loop
                   :for best :=  (first successors)
                   :and alternative :=  (second successors)
                   :if (&gt; (second best) f-limit) :do (list fail (second best))
                   :else :if (not (equal node fail) )
                   :do (list node cost)
                   :collect (rbfs best
                                  (+ cost (getdistance (first best) node) )
                                  (min f-limit (second alternative) ) goal)))))))
  </code></pre>
  
  <p>Now, the problem with this code is that the recursion never unwidnds. Using (trace rbfs) I get something like 1st, 2nd, 3rd, 4th, 5th call and then it repeats this 5th call all over again.</p>
  
  <p>So the question really is how to break recursion within a loop ;)</p>