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

Question

I have a recursive function that must be restored until it finds a specific result. However, in the body of my function, after my first recursive call, I could perform some other calculations, or possibly write again. But, if I recurs and find the result that I am looking for, then I would just like to stop any recursive work that I did and return this result to avoid unnecessary calculations.

In a regular recursive call, when you get into the “base case”, which returns to the called function, then returns to the called, and so on. I would like to know how easy it is to return the first time the function was called, and there is no need to return something for all these intermediate steps.

For my main 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 was written to illustrate what I mean about a function that does more calculations after a recursive call. And, as it is written, this does not even return the value that interests me, since I do some printouts after I return my value that excites me. (Note: the return-from command is extraneous here, since I could just write “x” in its place. Here, just draw parallels when I try to return to the top-level recursion in my second example below.)

Now, if I want to drop all the extra "Recursed!" I can wrap everything in a block and then just go back to this block:

EDIT: Here is a shell example for my source example. Now this example should be clearer.

 (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 the launch of this block continues until 10 "is found, and then returns to the top-level block without extraneous printing, just like I. But this seems like a really clumsy way to get this function. I would like to know if there is a standard or the "best" way to get this type of behavior.

Answer 1

DEFUN already installs the 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))) 

The elderly is the use of CATCH and THROW , which is a more dynamic design and thus allows you to exit through 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 already mentioned by Lars, there is even more room for programming a control thread like this.

Answer 2

You want some kind of non-local exit. There are several options: return-from , go , throw , signal .

Maybe some changes on this?

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

I believe that he does what you want, although many unnecessary traps can occur.

As always with Lisp, you can imagine that you have the perfect language for your problem, and write your program in that language. For instance. sort of

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

Then there is simply a programming question for implementing the new top-level-block and return-from-top-level macros.

The following is an invalid code example:

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