Während ich anfing, Lispeln zu lernen, bin ich auf den Ausdruck gestoßen tail-rekursiv. Was bedeutet es genau?
Während ich anfing, Lispeln zu lernen, bin ich auf den Ausdruck gestoßen tail-rekursiv. Was bedeutet es genau?
Betrachten Sie eine einfache Funktion, die die ersten N ganzen Zahlen addiert. (z.B. sum(5) = 1 + 2 + 3 + 4 + 5 = 15
).
Hier ist eine einfache JavaScript-Implementierung, die Rekursion verwendet:
function recsum(x) {
if (x===1) {
return x;
} else {
return x + recsum(x-1);
}
}
Wenn du angerufen hast recsum(5)
Dies würde der JavaScript-Interpreter bewerten:
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15
Beachten Sie, dass jeder rekursive Aufruf abgeschlossen sein muss, bevor der JavaScript-Interpreter beginnt, die Summe zu berechnen.
Hier ist eine Tail-rekursive Version der gleichen Funktion:
function tailrecsum(x, running_total=0) {
if (x===0) {
return running_total;
} else {
return tailrecsum(x-1, running_total+x);
}
}
Hier ist die Abfolge der Ereignisse, die auftreten würden, wenn Sie angerufen haben tailrecsum(5)
(was effektiv wäre tailrecsum(5, 0)
, wegen des Standardzweiten Arguments).
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15
Im tailrekursiven Fall wird bei jeder Auswertung des rekursiven Aufrufs der running_total
ist aktualisiert.
Hinweis: In der ursprünglichen Antwort wurden Beispiele aus Python verwendet. Diese wurden auf JavaScript umgestellt, da moderne JavaScript-Interpreter Unterstützung bieten Tail-Call-Optimierung aber Python-Interpreter nicht.
Im traditionelle RekursionDas typische Modell besteht darin, dass Sie zuerst Ihre rekursiven Aufrufe durchführen und dann den Rückgabewert des rekursiven Aufrufs verwenden und das Ergebnis berechnen. Auf diese Weise erhalten Sie das Ergebnis Ihrer Berechnung erst, wenn Sie von jedem rekursiven Aufruf zurückgekehrt sind.
Im Schwanzrekursion, führen Sie zuerst Ihre Berechnungen aus und führen Sie dann den rekursiven Aufruf aus, wobei Sie die Ergebnisse Ihres aktuellen Schritts an den nächsten rekursiven Schritt übergeben. Dies führt dazu, dass die letzte Aussage in Form von (return (recursive-function params))
. Grundsätzlich ist der Rückgabewert eines gegebenen rekursiven Schrittes derselbe wie der Rückgabewert des nächsten rekursiven Aufrufs.
Die Konsequenz daraus ist, dass Sie, sobald Sie bereit sind, Ihren nächsten rekursiven Schritt auszuführen, den aktuellen Stapelrahmen nicht mehr benötigen. Dies ermöglicht eine gewisse Optimierung. Mit einem entsprechend geschriebenen Compiler sollten Sie niemals einen Stack-Überlauf haben kichern mit einem rekursiven Tail-Aufruf. Verwenden Sie einfach den aktuellen Stapelrahmen für den nächsten rekursiven Schritt. Ich bin mir ziemlich sicher, dass Lisp das macht.
Ein wichtiger Punkt ist, dass die Tail-Rekursion im Wesentlichen der Schleifenbildung entspricht. Es geht nicht nur um Compiler-Optimierung, sondern um eine grundlegende Aussagekraft. Das geht in beide Richtungen: Sie können jede Schleife des Formulars nehmen
while(E) { S }; return Q
woher E
und Q
sind Ausdrücke und S
ist eine Abfolge von Anweisungen und wandelt sie in eine tail rekursive Funktion um
f() = if E then { S; return f() } else { return Q }
Na sicher, E
, S
, und Q
müssen definiert werden, um einige interessante Werte über einige Variablen zu berechnen. Zum Beispiel die Schleifenfunktion
sum(n) {
int i = 1, k = 0;
while( i <= n ) {
k += i;
++i;
}
return k;
}
entspricht der tail-rekursiven Funktion (en)
sum_aux(n,i,k) {
if( i <= n ) {
return sum_aux(n,i+1,k+i);
} else {
return k;
}
}
sum(n) {
return sum_aux(n,1,0);
}
(Dieses "Wrapping" der tailrekursiven Funktion mit einer Funktion mit weniger Parametern ist ein übliches Funktionsidiom.)
Dieser Auszug aus dem Buch Programmierung in Lua zeigt an wie man eine richtige Schwanzrekursion macht (in Lua, sollte aber auch bei Lisp gelten) und warum es besser ist.
EIN Schwanzanruf [Tail Rekursion] ist eine Art von gekleidet als Anruf. Ein Tail Call findet statt, wenn a Funktion ruft eine andere als ihre letzte auf Aktion, so hat es nichts anderes zu tun. Zum Beispiel im folgenden Code, der Anruf zu
g
ist ein Tail-Call:function f (x) return g(x) end
Nach
f
Anrufeg
Es hat nichts anderes machen. In solchen Situationen das Programm muss nicht zum Anrufer zurückkehren Funktion wenn die aufgerufene Funktion endet. Daher, nach dem Rückruf, Das Programm muss keine behalten Informationen über die aufrufende Funktion im Stapel. ...Weil ein richtiger Tail Call nein verwendet Stapelplatz, es gibt keine Grenze für die Anzahl der "verschachtelten" Tail-Aufrufe, die a Programm kann machen. Zum Beispiel können wir Rufen Sie die folgende Funktion mit an Zahl als Argument; es wird nie Überlauf den Stapel:
function foo (n) if n > 0 then return foo(n - 1) end end
... Wie ich bereits sagte, ist ein Tail Call ein irgendwie goto. Als solches, ziemlich nützlich Anwendung von richtigen Schwanz ruft herein Lua dient zum Programmieren von Zustandsautomaten. Solche Anwendungen können jeweils repräsentieren Zustand durch eine Funktion; den Staat wechseln ist, zu einem bestimmten zu gehen (oder zu nennen) Funktion. Als ein Beispiel, lassen Sie uns Betrachten Sie ein einfaches Labyrinth-Spiel. Das Labyrinth hat mehrere Zimmer mit jeweils bis zu vier Türen: Norden, Süden, Osten und Westen. Bei jedem Schritt gibt der Benutzer ein ein Bewegungsrichtung. Wenn da eine Tür ist In dieser Richtung geht der Benutzer zu der entsprechende Raum; ansonsten der Programm druckt eine Warnung. Das Ziel ist von einem anfänglichen Raum zu einem Finale zu gehen Zimmer.
Dieses Spiel ist eine typische Staatsmaschine, wo der aktuelle Raum der Staat ist. Wir können ein solches Labyrinth mit einem implementieren Funktion für jeden Raum. Wir benutzen Schwanz Anrufe von einem Raum zu bewegen Ein weiterer. Ein kleines Labyrinth mit vier Räumen könnte so aussehen:
function room1 () local move = io.read() if move == "south" then return room3() elseif move == "east" then return room2() else print("invalid move") return room1() -- stay in the same room end end function room2 () local move = io.read() if move == "south" then return room4() elseif move == "west" then return room1() else print("invalid move") return room2() end end function room3 () local move = io.read() if move == "north" then return room1() elseif move == "east" then return room4() else print("invalid move") return room3() end end function room4 () print("congratulations!") end
Sie sehen also, wenn Sie einen rekursiven Aufruf wie:
function x(n)
if n==0 then return 0
n= n-2
return x(n) + 1
end
Dies ist nicht tail-rekursiv, da Sie nach dem rekursiven Aufruf immer noch Aufgaben in dieser Funktion ausführen müssen (1). Wenn Sie eine sehr hohe Zahl eingeben, wird wahrscheinlich ein Stapelüberlauf verursacht.
Bei Verwendung der regulären Rekursion drückt jeder rekursive Aufruf einen weiteren Eintrag auf den Aufrufstapel. Wenn die Rekursion abgeschlossen ist, muss die App jeden Eintrag wieder ganz zurückgeben.
Bei der Tail-Rekursion kann der Compiler den Stack auf einen Eintrag reduzieren, so dass Sie Speicherplatz sparen. Eine große rekursive Abfrage kann tatsächlich einen Stack-Überlauf verursachen.
Grundsätzlich können Tail-Rekursionen in Iteration optimiert werden.
Anstatt es mit Worten zu erklären, hier ist ein Beispiel. Dies ist eine Scheme-Version der faktoriellen Funktion:
(define (factorial x)
(if (= x 0) 1
(* x (factorial (- x 1)))))
Hier ist eine faktorielle Version, die tail-rekursiv ist:
(define factorial
(letrec ((fact (lambda (x accum)
(if (= x 0) accum
(fact (- x 1) (* accum x))))))
(lambda (x)
(fact x 1))))
Sie werden in der ersten Version feststellen, dass der rekursive Aufruf zur Tatsache in den Multiplikationsausdruck eingegeben wird, und daher muss der Zustand auf dem Stapel gespeichert werden, wenn der rekursive Aufruf ausgeführt wird. In der tailrekursiven Version wartet kein anderer S-Ausdruck auf den Wert des rekursiven Aufrufs, und da keine weitere Arbeit zu erledigen ist, muss der Zustand nicht auf dem Stapel gespeichert werden. In der Regel verwenden rekursive Funktionen des Schemas stack stack space.
Die Jargon-Datei sagt Folgendes über die Definition der Tail-Rekursion:
Schwanzrekursion /n./
Wenn Sie es nicht schon satt haben, sehen Sie sich die Schwanzrekursion an.
Die Tail-Rekursion bezieht sich auf den rekursiven Aufruf, der in der letzten logischen Anweisung im rekursiven Algorithmus zuletzt ist.
Typischerweise haben Sie in der Rekursion ein Basis-Fall Das stoppt die rekursiven Aufrufe und beginnt mit dem Aufruf des Aufruf-Stacks. Um ein klassisches Beispiel zu verwenden, obwohl es mehr C-ish als Lisp ist, veranschaulicht die Fakultätefunktion die Tail-Rekursion. Der rekursive Aufruf erfolgt nach Überprüfung des Grundzustands
factorial(x, fac) {
if (x == 1)
return fac;
else
return factorial(x-1, x*fac);
}
Beachten Sie, dass der anfängliche Aufruf von factorial factorial (n, 1) sein muss, wobei n die Nummer ist, für die das factorial berechnet werden soll.
Es bedeutet, dass Sie den Anweisungszeiger nicht einfach auf den Stack schieben müssen, sondern einfach an den Anfang einer rekursiven Funktion springen und die Ausführung fortsetzen können. Dadurch können Funktionen unbegrenzt recursen, ohne den Stack zu überlasten.
Ich schrieb ein Blog Post zu dem Thema, das grafische Beispiele dafür hat, wie die Stack-Frames aussehen.