Zurück zum Aufruf der obersten Ebene einer rekursiven Funktion in Lisp

Question

Ich habe eine rekursive Funktion, die rekursiv ist, bis sie ein bestimmtes Ergebnis findet. Jedoch könnte ich im Körper meiner Funktion nach meinem ersten rekursiven Aufruf einige andere Berechnungen durchführen oder möglicherweise erneut rekursieren. Aber wenn ich das Ergebnis, das ich suche, rekursiv finde, dann möchte ich einfach von jedem rekursiven Vorgang, den ich gemacht habe, absehen und dieses Ergebnis zurückgeben, um unnötige Berechnungen zu vermeiden.

In einem normalen rekursiven Aufruf, sobald Sie zu dem "Basisfall", der an die aufgerufene Funktion zurückgegeben wird, erhalten, dann wird das an die aufgerufen, die es aufgerufen hat, und so weiter. Ich würde gerne wissen, wie ich zum ersten Mal, wenn die Funktion aufgerufen wird, zurückkehren kann und nicht für all diese Zwischenschritte etwas zurückgeben muss.

Für meinen Grund Rekursion ich eine Funktion wie diese schreiben könnte:

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

Es wurde geschrieben zu veranschaulichen, was ich meine über die Funktion mehr Berechnungen nach einem rekursiven Aufruf ausgeführt wird. Und, wie geschrieben, gibt dies nicht einmal den Wert zurück, an dem ich interessiert bin, da ich einige Ausdrucke mache, nachdem ich den Wert zurückgegeben habe, der mir wichtig ist. (Anmerkung: Der Return-from-Befehl ist hier irrelevant, da ich einfach "x" an seiner Stelle schreiben könnte. Es ist nur da, um Parallelen zu ziehen, wenn ich versuche, in meinem zweiten Beispiel zur Top-Level-Rekursion zurückzukehren.)

Nun, wenn ich all diese Extra "Recursed!" Drucken Ich könnte alles in einem Block umschließen und dann einfach zu diesem Block zurückkehren:

EDIT: Hier ist ein Funktions-Wrapper für mein ursprüngliches Beispiel. Dieses Beispiel sollte jetzt klarer sein.

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

Und diesen Block am Laufen hält, bis 10 gehen „gefunden“ und kehrt dann in der Top-Level-Block ohne Fremddruck, wie nur ich wollte. Aber das scheint eine wirklich klobige Art zu sein, dieses Feature zu bekommen. Ich würde gerne wissen, ob es einen Standard oder "besten" Weg gibt, diese Art von Verhalten zu bekommen.

Answer 1

DEFUN bereits setzt einen lexikalischen Block up:

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

älter ist die Verwendung von CATCH und THROW, die eine dynamischere Konstrukts ist und ermöglicht somit eine Ausfahrt über Funktionen:

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

Wie von Lars erwähnt, gibt es sogar noch mehr Möglichkeiten, den Kontrollfluss so zu programmieren.

Answer 2

Sie möchten eine Art nicht-lokalen Ausgang. Es gibt ein paar Möglichkeiten: return-from, go, throw, signal.

Vielleicht eine Variation dazu?

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

Ich glaube, es tut, was Sie wollen, obwohl es eine Menge nutzloser sein kann los zu kontrollieren.

Wie immer bei Lisp können Sie sich vorstellen, dass es eine perfekte Sprache für Ihr Problem gibt, und schreiben Sie Ihr Programm in dieser Sprache. Z.B. so etwas wie

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

Dann gibt es nur eine einfach eine Frage der Programmierung die neuen Makros top-level-block und return-from-top-level zu implementieren.

Unvollkommen Beispielcode folgt:

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