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.

Unalloyed

In your example with a block, "Recursed!" is never printed, so why is it there in the first place? I believe your real code has something more to it which has been lost in your example. – Vanmeter

i.e., (defun recurse (x) (if (= x 10) x (recurse (+ x 1)))) does just what you want. – Vanmeter

You misunderstand my question. The point of the print inside my function is to demonstrate a recursive function which might do things after a recursive call. In the first example you see that each of the print functions gets run because they happen after every time the recursion returns. The second example was written to show a potential way to get around this issue by returning all the way to the top level of my recursive call, thus not doing any further commands. I left the print command in there precisely to show that in that example it won't get run. – Unalloyed

But in the second example it is never executed, not even for values below 10, so it's essentially dead code. Why jump over dead code? I think you have a XY-problem here, and more code would be better in this case. – Vanmeter

I think you're too concerned about the actual code and not the concept it represents. In a normal recursive call once you get to the "base case" that gets returned to the function that called it, every return only goes up one level of recursion and then another return happens until the original call. (This is the first example.) I'd like to know how to just return from the original call in a single step once my "base case" is found. Example 2 shows a (bad) way to emulate this idea using the same function from the first example. – Unalloyed

@Unalloyed I think I see the point you're making about recursive calls in non-tail position (i.e., where something happens afterwards. The point uselpa is making, though, is valid too: the body of the inner recurse is an if where the then-part is an immediate return (because of return-from) and the else is a recursive call to something that that will eventually hit the return-from. So none of those prints can ever be executed. That said, this question shows a good amount of research, and makes a good attempt at illustrating the behavior you're talking about. +1 – Bhayani

But also note that in the case of tail-recursion where there isn't something after the recursive call, some implementations can perform tail-call elimination, which means that the return across all those function calls will actually be immediate. – Bhayani

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.

Revanche

The first example works fine, but is there a particular "best" or "preferred" way to get this control flow since you mention multiple ways? – Unalloyed

@Nyles: The first is common for nested functions. – Revanche

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))

Selmner