Return to top-level call of a recursive function in Lisp

Question

I have a recursive function which needs to recurse until it finds a certain result. However in the body of my function after my first recursive call I might do some other calculations or possibly recurse again. But, if I recurse and find the result I'm looking for, then I'd like to just stop out of any recursive I've been doing and return that result to avoid doing unnecessary computations.

In a normal recursive call once you get to the "base case" that gets returned to the function that called, then that gets returned to the one that called it, and so on. I'd like to know how to just return to the very first time the function was called, and not have to return something for all those intermediate steps.

For my basic recursion I could write a function like this:

(defun recurse (x)
   (if (= x 10)
       (return-from recurse x)
       (progn (recurse (+ x 1)) (print "Recursed!")))))
(recurse 1)

It has been written to illustrate what I mean about the function running more computations after a recursive call. And, as written this doesn't even return the value I'm interested in since I do some printings after I've returned the value I care about. (Note: The return-from command is extraneous here as I could just write "x" in its place. It's just there to draw parallels for when I try to return to the top level recursion in my second example below.)

Now, if I want to ditch all those extra "Recursed!" printings I could encase everything in a block and then just return to that block instead:

EDIT: Here is a function wrapper for my original example. This example should be clearer now.

(defun recurse-to-top (start)
  (block top-level
    (labels ((recurse (x)
               (if (= x 10)
                   (return-from top-level x)
                   (progn (recurse (+ x 1)) (print "Recursed!")))))
      (recurse start))))

And running this block keeps going until 10 "is found" and then returns to from the top-level block with no extraneous printing, just like I wanted. But, this seems like a really clunky way to get this feature. I'd like to know if there's a standard or "best" way for getting this type of behavior.

Answer 1

DEFUN already sets up a lexical block:

(defun recurse (start)
  (labels ((recurse-aux (x)
             (case x
               (10 (return-from recurse x))
               (15 x)
               (otherwise
                 (recurse-aux (+ x 1))
                 (print "Recursed!")))))
    (recurse-aux start)))

Older is the use of CATCH and THROW, which is a more dynamic construct and thus allows an exit across functions:

(defun recurse (start)
  (catch 'recurse-exit
    (recurse-aux start)))

(defun recurse-aux  (x)
  (case x
    (10 (throw 'recurse-exit x))
    (15 x)
    (otherwise
     (recurse-aux (+ x 1))
     (print "Recursed!")))))
      (recurse-aux start))))

As mentioned by Lars, there are even more way to program control flow like this.

Answer 2

You want some kind of non-local exit. There are a few choices: return-from, go, throw, signal.

Maybe some variation on this?

(defun recurse (x &optional (tag 'done))
  (catch tag
    (when (= x 10)
      (throw 'done x))
    (recurse (1+ x) nil)
    (print "Cursed!")))

I believe it does what you want, although there may be a lot of needless catching going on.

As always with Lisp, you can imagine there is a perfect language for your problem, and write your program in that language. E.g. something like

(defun recurse (x)
  (top-level-block recurse
    (when (= x 10)
      (return-from-top-level recurse x))
    (recurse (1+ x))
    (print "Cursed!")))

Then there is just a simple matter of programming to implement the new macros top-level-block and return-from-top-level.

Imperfect sample code follows:

(defmacro top-level-block (name &body body)
  `(if (boundp ',name)
       (progn ,@body)
       (catch ',name
         (let ((,name t))
           (declare (special ,name))
           ,@body))))

(defmacro return-from-top-level (name value)
  `(throw ',name ,value))