The problem is that we are searching an infinite tree, and the depth-first search strategy just dives down the left-hand branch at every step. The only way to stop the doomed search is to type an interrupt character.

An alternative strategy is breadth-first search, where the shortest path is extended first at each step. It can be implemented simply by appending the new successor states to the end of the existing states:

(defun prepend (x y) "Prepend y t o s t a r t o f x" (append y x))

(defun b r e a d t h - f i r s t -search ( s t a r t goal-p successors)

"Search old states f i r s t u n t i l goal i s reached. "

(tree-search ( l i s t s t a r t ) goal-p successors #'prepend))