Was ist Schwanzrekursion?
https://stackoverflow.com/questions/33923
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Als ich anfing, Lispeln zu lernen, bin ich auf den Begriff gestoßen Schwanzrekursiv.Was bedeutet es genau?
Lösung
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 Sie angerufen haben recsum(5), das würde der JavaScript-Interpreter auswerten:
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 tatsächlich mit der Berechnung der Summe beginnt.
Hier ist eine tail-rekursive Version derselben 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 bei einem Anruf eintreten würden tailrecsum(5), (was effektiv wäre tailrecsum(5, 0), wegen des standardmäßigen zweiten Arguments).
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15
Im tail-rekursiven Fall wird bei jeder Auswertung des rekursiven Aufrufs die running_total ist aktualisiert.
Notiz:Die ursprüngliche Antwort verwendete Beispiele aus Python.Diese wurden auf JavaScript umgestellt, da moderne JavaScript-Interpreter dies unterstützen Tail-Call-Optimierung Python-Interpreter jedoch nicht.
Andere Tipps
In traditionelle Rekursion, Das typische Modell besteht darin, dass Sie zuerst Ihre rekursiven Aufrufe ausführen und dann den Rückgabewert des rekursiven Aufrufs nehmen und das Ergebnis berechnen.Auf diese Weise erhalten Sie das Ergebnis Ihrer Berechnung erst, wenn Sie von jedem rekursiven Aufruf zurückgekehrt sind.
In Schwanzrekursion, führen Sie zuerst Ihre Berechnungen durch und führen 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 die Form hat (return (recursive-function params)). Grundsätzlich ist der Rückgabewert eines bestimmten rekursiven Schritts derselbe wie der Rückgabewert des nächsten rekursiven Aufrufs.
Dies hat zur Folge, dass Sie den aktuellen Stapelrahmen nicht mehr benötigen, sobald Sie bereit sind, Ihren nächsten rekursiven Schritt auszuführen.Dies ermöglicht eine gewisse Optimierung.Tatsächlich sollte es bei einem entsprechend geschriebenen Compiler nie zu einem Stapelüberlauf kommen kichern mit einem tail-rekursiven Aufruf.Verwenden Sie einfach den aktuellen Stapelrahmen für den nächsten rekursiven Schritt wieder.Ich bin mir ziemlich sicher, dass Lisp das tut.
Ein wichtiger Punkt ist, dass die Schwanzrekursion im Wesentlichen einer Schleife entspricht.Dabei geht es nicht nur um die Compiler-Optimierung, sondern um eine grundlegende Tatsache der Ausdruckskraft.Das geht in beide Richtungen:Sie können eine beliebige Schleife des Formulars verwenden
while(E) { S }; return Q
Wo E Und Q sind Ausdrücke und S ist eine Folge von Anweisungen und wandelt sie in eine rekursive Endfunktion um
f() = if E then { S; return f() } else { return Q }
Natürlich, E, S, Und Q müssen definiert werden, um einen interessanten Wert für einige Variablen zu berechnen.Zum Beispiel die Looping-Funktion
sum(n) {
int i = 1, k = 0;
while( i <= n ) {
k += i;
++i;
}
return k;
}
ist äquivalent zu der/den schwanzrekursiven 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 „Umschließen“ der schwanzrekursiven Funktion mit einer Funktion mit weniger Parametern ist eine gängige funktionale Redewendung.)
Dieser Auszug aus dem Buch Programmieren in Lua zeigt an wie man eine richtige Schwanzrekursion durchführt (in Lua, sollte aber auch für Lisp gelten) und warum es besser ist.
A Rückruf Tail Rekursion] ist eine Art von Goto als Anruf.Ein Schwanzaufruf erfolgt, wenn eine Funktion eine andere als letzte Aktion anruft, so dass sie nichts anderes zu tun hat.Zum Beispiel im folgenden Code der Anruf an
gist ein Tail Call:function f (x) return g(x) endNach
fAnrufeg, Es hat nichts anderes zu tun.In solchen Situationen muss das Programm nicht zur Aufruffunktion zurückkehren, wenn die aufgerufene Funktion endet.Nach dem Schwanzaufruf muss das Programm daher keine Informationen über die Aufruffunktion im Stapel aufbewahren....Da ein richtiger Schwanzanruf keinen Stack -Speicherplatz verwendet, gibt es keine Begrenzung für die Anzahl der "verschachtelten" Schwanzanrufe, die ein Programm erstellen kann.Zum Beispiel können wir die folgende Funktion mit einer beliebigen Zahl als Argument aufrufen.Es wird den Stapel niemals überlaufen:
function foo (n) if n > 0 then return foo(n - 1) end end...Wie ich bereits sagte, ist ein Schwanzanruf eine Art Goto.Daher ist eine sehr nützliche Anwendung von ordnungsgemäßen Schwanzaufrufen in Lua für Programmiermaschinen gedacht.Solche Anwendungen können jeden Zustand durch eine Funktion darstellen;Status zu ändern bedeutet, eine bestimmte Funktion zu (oder aufzurufen).Betrachten wir als Beispiel ein einfaches Labyrinthspiel.Das Labyrinth hat mehrere Räume mit jeweils bis zu vier Türen:Nord, Süd, Osten und West.Bei jedem Schritt tritt der Benutzer eine Bewegungsrichtung ein.Wenn sich in dieser Richtung eine Tür befindet, geht der Benutzer in den entsprechenden Raum.Ansonsten druckt das Programm eine Warnung.Das Ziel ist es, von einem Anfangsraum in einen letzten Raum zu gelangen.
Dieses Spiel ist eine typische Staatsmaschine, in der der aktuelle Raum der Staat ist.Wir können ein solches Labyrinth mit einer Funktion für jeden Raum implementieren.Wir verwenden Schwanzaufrufe, um von einem Raum in einen anderen zu wechseln.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 durchführen wie:
function x(n)
if n==0 then return 0
n= n-2
return x(n) + 1
end
Dies ist nicht endrekursiv, da Sie in dieser Funktion nach dem rekursiven Aufruf noch Dinge zu tun haben (1 hinzufügen).Wenn Sie eine sehr hohe Zahl eingeben, kommt es wahrscheinlich zu einem Stapelüberlauf.
Bei der regulären Rekursion schiebt jeder rekursive Aufruf einen anderen Eintrag auf den Aufrufstapel.Wenn die Rekursion abgeschlossen ist, muss die App jeden Eintrag ganz nach unten entfernen.
Mit der Schwanzrekursion kann der Compiler je nach Sprache den Stapel möglicherweise auf einen Eintrag reduzieren, sodass Sie Stapelplatz sparen. Eine große rekursive Abfrage kann tatsächlich einen Stapelüberlauf verursachen.
Grundsätzlich können Tail-Rekursionen in Iterationen optimiert werden.
Anstatt es mit Worten zu erklären, hier ein Beispiel.Dies ist eine Scheme-Version der Fakultätsfunktion:
(define (factorial x)
(if (= x 0) 1
(* x (factorial (- x 1)))))
Hier ist eine Version von „factorial“, die schwanzrekursiv 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 von fact in den Multiplikationsausdruck eingespeist wird und daher der Status beim Durchführen des rekursiven Aufrufs auf dem Stapel gespeichert werden muss.In der tail-rekursiven Version wartet kein anderer S-Ausdruck auf den Wert des rekursiven Aufrufs, und da keine weitere Arbeit erforderlich ist, muss der Status nicht auf dem Stapel gespeichert werden.In der Regel verwenden Scheme-Tail-rekursive Funktionen konstanten Stapelspeicherplatz.
In der Jargon-Datei heißt es zur Definition der Tail-Rekursion:
Schwanzrekursion /N./
Wenn Sie es noch nicht satt haben, schauen Sie sich Schwanzrekursion an.
Schwanzrekursion bezieht sich darauf, dass der rekursive Aufruf der letzte in der letzten Logikanweisung im rekursiven Algorithmus ist.
Normalerweise haben Sie bei einer Rekursion eine Basisfall Dadurch werden die rekursiven Aufrufe gestoppt und der Aufrufstapel wird geöffnet.Um ein klassisches Beispiel zu verwenden, obwohl es eher an C als an Lisp erinnert: Die Fakultätsfunktion veranschaulicht die Tail-Rekursion.Der rekursive Aufruf erfolgt nach Überprüfung des Grundzustands.
factorial(x, fac=1) {
if (x == 1)
return fac;
else
return factorial(x-1, x*fac);
}
Der erste Anruf bei Factorial wäre factorial(n) Wo fac=1 (Standardwert) und n ist die Zahl, für die die Fakultät berechnet werden soll.
Das bedeutet, dass Sie, anstatt den Befehlszeiger auf den Stapel verschieben zu müssen, einfach an den Anfang einer rekursiven Funktion springen und mit der Ausführung fortfahren können.Dadurch können Funktionen auf unbestimmte Zeit rekursiv ausgeführt werden, ohne dass der Stapel überläuft.
Ich habe ein geschrieben Blog Beitrag zu diesem Thema, der grafische Beispiele dafür enthält, wie die Stapelrahmen aussehen.
Hier ist ein kurzer Codeausschnitt, der zwei Funktionen vergleicht.Die erste ist die traditionelle Rekursion zum Ermitteln der Fakultät einer gegebenen Zahl.Der zweite verwendet die Schwanzrekursion.
Sehr einfach und intuitiv zu verstehen.
Eine einfache Möglichkeit, festzustellen, ob eine rekursive Funktion eine Schwanzrekursion ist, besteht darin, dass sie im Basisfall einen konkreten Wert zurückgibt.Das bedeutet, dass es weder 1 noch true oder ähnliches zurückgibt.Es wird höchstwahrscheinlich eine Variante eines der Methodenparameter zurückgeben.
Eine andere Möglichkeit besteht darin, festzustellen, ob der rekursive Aufruf frei von Additionen, Arithmetik, Modifikation usw. ist.Das heißt, es ist nichts anderes als ein rein rekursiver Aufruf.
public static int factorial(int mynumber) {
if (mynumber == 1) {
return 1;
} else {
return mynumber * factorial(--mynumber);
}
}
public static int tail_factorial(int mynumber, int sofar) {
if (mynumber == 1) {
return sofar;
} else {
return tail_factorial(--mynumber, sofar * mynumber);
}
}
Für mich der beste Weg, es zu verstehen tail call recursion ist ein Sonderfall der Rekursion, bei dem die letzter Aufruf(oder der Tail Call) ist die Funktion selbst.
Vergleich der in Python bereitgestellten Beispiele:
def recsum(x):
if x == 1:
return x
else:
return x + recsum(x - 1)
^REKURSION
def tailrecsum(x, running_total=0):
if x == 0:
return running_total
else:
return tailrecsum(x - 1, running_total + x)
^TAIL-REKURSION
Wie Sie in der allgemeinen rekursiven Version sehen können, ist der letzte Aufruf im Codeblock x + recsum(x - 1).Also nach dem Anruf recsum Methode, es gibt eine andere Operation, die ist x + ...
In der tail-rekursiven Version ist jedoch der letzte Aufruf (oder der Tail-Call) im Codeblock tailrecsum(x - 1, running_total + x) Dies bedeutet, dass der letzte Aufruf an die Methode selbst erfolgt und danach keine Operation ausgeführt wird.
Dieser Punkt ist wichtig, da die Tail-Rekursion, wie hier gezeigt, den Speicher nicht vergrößert, denn wenn die zugrunde liegende VM eine Funktion sieht, die sich selbst an einer Tail-Position aufruft (der letzte auszuwertende Ausdruck in einer Funktion), eliminiert sie den aktuellen Stack-Frame, wodurch der aktuelle Stack-Frame gelöscht wird ist als Tail Call Optimization (TCO) bekannt.
BEARBEITEN
NB.Bedenken Sie, dass das obige Beispiel in Python geschrieben ist, dessen Laufzeit TCO nicht unterstützt.Dies ist nur ein Beispiel, um den Punkt zu verdeutlichen.TCO wird in Sprachen wie Scheme, Haskell usw. unterstützt
In Java ist hier eine mögliche endrekursive Implementierung der Fibonacci-Funktion:
public int tailRecursive(final int n) {
if (n <= 2)
return 1;
return tailRecursiveAux(n, 1, 1);
}
private int tailRecursiveAux(int n, int iter, int acc) {
if (iter == n)
return acc;
return tailRecursiveAux(n, ++iter, acc + iter);
}
Vergleichen Sie dies mit der standardmäßigen rekursiven Implementierung:
public int recursive(final int n) {
if (n <= 2)
return 1;
return recursive(n - 1) + recursive(n - 2);
}
Hier ist ein Common Lisp-Beispiel, das Fakultäten mithilfe der Tail-Rekursion durchführt.Aufgrund der stapellosen Natur könnte man wahnsinnig große faktorielle Berechnungen durchführen ...
(defun ! (n &optional (product 1))
(if (zerop n) product
(! (1- n) (* product n))))
Und dann könntest du es zum Spaß versuchen (format nil "~R" (! 25))
Ich bin kein Lisp-Programmierer, aber ich denke Das wird helfen.
Im Grunde handelt es sich um einen Programmierstil, bei dem der rekursive Aufruf das letzte ist, was Sie tun.
Kurz gesagt, eine Tail-Rekursion hat den rekursiven Aufruf als zuletzt Anweisung in der Funktion, damit diese nicht auf den rekursiven Aufruf warten muss.
Das ist also eine Tail-Rekursion, d.h.N(x - 1, p * x) ist die letzte Anweisung in der Funktion, bei der der Compiler klugerweise herausgefunden hat, dass sie für eine For-Schleife (Fakultät) optimiert werden kann.Der zweite Parameter p trägt den Zwischenproduktwert.
function N(x, p) {
return x == 1 ? p : N(x - 1, p * x);
}
Dies ist die nicht-tail-rekursive Art, die obige Fakultätsfunktion zu schreiben (obwohl einige C++-Compiler sie möglicherweise trotzdem optimieren können).
function N(x) {
return x == 1 ? 1 : x * N(x - 1);
}
aber das ist nicht:
function F(x) {
if (x == 1) return 0;
if (x == 2) return 1;
return F(x - 1) + F(x - 2);
}
Ich habe einen langen Beitrag mit dem Titel „Grundlegendes zur Tail-Rekursion – Visual Studio C++ – Assembly-Ansicht"
Hier ist eine Perl 5-Version davon tailrecsum bereits erwähnte Funktion.
sub tail_rec_sum($;$){
my( $x,$running_total ) = (@_,0);
return $running_total unless $x;
@_ = ($x-1,$running_total+$x);
goto &tail_rec_sum; # throw away current stack frame
}
Dies ist ein Auszug aus Struktur und Interpretation von Computerprogrammen über Schwanzrekursion.
Bei der Kontrast Iteration und Rekursion müssen wir darauf achten, den Begriff eines rekursiven Prozesses mit dem Begriff eines rekursiven Verfahrens nicht zu verwechseln.Wenn wir ein Verfahren als rekursiv beschreiben, beziehen wir uns auf die syntaktische Tatsache, dass sich die Verfahrensdefinition (entweder direkt oder indirekt) auf das Verfahren selbst bezieht.Wenn wir jedoch einen Prozess als ein Muster beschreiben, das beispielsweise linear rekursiv ist, sprechen wir darüber, wie sich der Prozess entwickelt, und nicht über die Syntax, wie ein Verfahren geschrieben wird.Es mag beunruhigend erscheinen, dass wir uns auf ein rekursives Verfahren wie die Tatsachen-IT-Erzeugung eines iterativen Prozesses beziehen.Der Prozess ist jedoch wirklich iterativ:Sein Zustand wird vollständig von seinen drei staatlichen Variablen erfasst, und ein Interpreter muss nur drei Variablen im Auge behalten, um den Prozess auszuführen.
Ein Grund, warum die Unterscheidung zwischen Prozess und Verfahren verwirrend sein kann, ist, dass die meisten Implementierungen gemeinsamer Sprachen (einschließlich ADA, Pascal und C) so ausgelegt sind, dass die Interpretation eines rekursiven Verfahrens eine Menge Speicher verbraucht, die mit dem wächst Anzahl der Verfahrensaufrufe, auch wenn der beschriebene Prozess im Prinzip iterativ ist.Infolgedessen können diese Sprachen iterative Prozesse nur beschreiben, indem sie auf spezielle „Schleifenkonstrukte“ zurückgreifen, z. B. wiederholen, bis, für und während. Die Umsetzung des Schemas teilt diesen Defekt nicht.Es wird einen iterativen Prozess im konstanten Raum ausführen, auch wenn der iterative Prozess durch ein rekursives Verfahren beschrieben wird.Eine Implementierung mit dieser Eigenschaft heißt Tail-Recursive. Mit einer schwanzrezisiven Implementierung kann die Iteration mit dem ordentlichen Verfahrensaufrufmechanismus ausgedrückt werden, so dass spezielle Iterationskonstrukte nur als syntaktischer Zucker nützlich sind.
Schwanzrekursion ist das Leben, das Sie gerade führen.Sie recyceln immer wieder denselben Stapelrahmen, da es keinen Grund oder Mittel gibt, zu einem „vorherigen“ Rahmen zurückzukehren.Die Vergangenheit ist vorbei und kann abgelegt werden.Sie erhalten einen Frame, der sich für immer in die Zukunft bewegt, bis Ihr Prozess unweigerlich abstürzt.
Die Analogie versagt, wenn man bedenkt, dass einige Prozesse möglicherweise zusätzliche Frames verwenden, aber dennoch als tail-rekursiv gelten, wenn der Stapel nicht unendlich wächst.
Eine Schwanzreursion ist eine rekursive Funktion, bei der sich die Funktion am Ende ("Schwanz") der Funktion aufruft, in der nach der Rückgabe des rekursiven Aufrufs keine Berechnung durchgeführt wird.Viele Compiler optimieren, um einen rekursiven Aufruf in einen rekursiven Schwanz oder einen iterativen Anruf zu ändern.
Betrachten Sie das Problem der Berechnung der Fakultät einer Zahl.
Ein einfacher Ansatz wäre:
factorial(n):
if n==0 then 1
else n*factorial(n-1)
Angenommen, Sie rufen factial(4) auf.Der Rekursionsbaum wäre:
factorial(4)
/ \
4 factorial(3)
/ \
3 factorial(2)
/ \
2 factorial(1)
/ \
1 factorial(0)
\
1
Die maximale Rekursionstiefe beträgt im obigen Fall O(n).
Betrachten Sie jedoch das folgende Beispiel:
factAux(m,n):
if n==0 then m;
else factAux(m*n,n-1);
factTail(n):
return factAux(1,n);
Der Rekursionsbaum für factTail(4) wäre:
factTail(4)
|
factAux(1,4)
|
factAux(4,3)
|
factAux(12,2)
|
factAux(24,1)
|
factAux(24,0)
|
24
Auch hier beträgt die maximale Rekursionstiefe O(n), aber keiner der Aufrufe fügt dem Stapel eine zusätzliche Variable hinzu.Daher kann der Compiler auf einen Stapel verzichten.
Um einige der Kernunterschiede zwischen Tail-Call-Rekursion und Nicht-Tail-Call-Rekursion zu verstehen, können wir die .NET-Implementierungen dieser Techniken untersuchen.
Hier ist ein Artikel mit einigen Beispielen in C#, F# und C++\CLI: Abenteuer in der Schwanzrekursion in C#, F# und C++\CLI.
C# ist im Gegensatz zu F# nicht für die Tail-Call-Rekursion optimiert.
Die prinzipiellen Unterschiede betreffen Schleifen vs.Lambda-Kalkül.C# wurde unter Berücksichtigung von Schleifen entwickelt, während F# auf den Prinzipien der Lambda-Kalküle basiert.Ein sehr gutes (und kostenloses) Buch über die Prinzipien der Lambda-Kalküle finden Sie unter Struktur und Interpretation von Computerprogrammen, von Abelson, Sussman und Sussman.
Bezüglich Tail Calls in F# finden Sie einen sehr guten Einführungsartikel unter Detaillierte Einführung in Tail Calls in F#.Abschließend finden Sie hier einen Artikel, der den Unterschied zwischen Nicht-Tail-Rekursion und Tail-Call-Rekursion (in F#) behandelt: Tail-Rekursion vs.Nicht-Tail-Rekursion in Fis.
Wenn Sie mehr über einige der Designunterschiede der Tail-Call-Rekursion zwischen C# und F# erfahren möchten, lesen Sie Generieren von Tail-Call-Opcode in C# und F#.
Wenn Sie wissen möchten, welche Bedingungen den C#-Compiler daran hindern, Tail-Call-Optimierungen durchzuführen, lesen Sie diesen Artikel: JIT-CLR-Tail-Call-Bedingungen.
Es gibt zwei grundlegende Arten von Rekursionen: Kopfrekursion Und Schwanzrekursion.
In Kopfrekursion, Eine Funktion macht ihren rekursiven Anruf und führt dann einige weitere Berechnungen durch, was beispielsweise das Ergebnis des rekursiven Aufrufs verwendet.
In einem Schwanz rekursiv Funktion, alle Berechnungen erfolgen zuerst und der rekursive Anruf ist das Letzte, was passiert.
Genommen von Das super toller Beitrag.Bitte denken Sie darüber nach, es zu lesen.
Unter Rekursion versteht man eine Funktion, die sich selbst aufruft.Zum Beispiel:
(define (un-ended name)
(un-ended 'me)
(print "How can I get here?"))
Tail-Rekursion bedeutet die Rekursion, die die Funktion abschließt:
(define (un-ended name)
(print "hello")
(un-ended 'me))
Sehen Sie, das Letzte, was eine nicht beendete Funktion (Prozedur im Scheme-Jargon) tut, ist, sich selbst aufzurufen.Ein weiteres (nützlicheres) Beispiel ist:
(define (map lst op)
(define (helper done left)
(if (nil? left)
done
(helper (cons (op (car left))
done)
(cdr left))))
(reverse (helper '() lst)))
In der Hilfsprozedur ist das LETZTE, was es tut, wenn die linke Seite nicht nil ist, sich selbst aufzurufen (AFTER cons etwas und cdr etwas).Dies ist im Grunde die Art und Weise, wie Sie eine Liste zuordnen.
Die Tail-Rekursion hat den großen Vorteil, dass der Interpreter (oder Compiler, abhängig von der Sprache und dem Anbieter) sie optimieren und in etwas umwandeln kann, das einer While-Schleife entspricht.Tatsächlich werden in der Scheme-Tradition die meisten „for“- und „while“-Schleifen in Form einer Endrekursion ausgeführt (soweit ich weiß, gibt es kein for und while).
Auf diese Frage gibt es viele tolle Antworten ...Aber ich kann nicht anders, als mich mit einer alternativen Einstellung zu machen, wie man "Schwanzrekursion" oder zumindest "richtige Schwanzrekursion" definiert. Nämlich:Sollte man es als Eigenschaft eines bestimmten Ausdrucks in einem Programm betrachten?Oder sollte man es als eine Eigenschaft eines betrachten Implementierung einer Programmiersprache?
Für mehr zur letzteren Ansicht gibt es einen Klassiker Papier von Will Clinger, „Proper Tail Recursion and Space Efficiency“ (PLDI 1998), der „Proper Tail Recursion“ als Eigenschaft einer Programmiersprachenimplementierung definiert.Die Definition ist so aufgebaut, dass Implementierungsdetails ignoriert werden können (z. B. ob der Aufrufstapel tatsächlich über den Laufzeitstapel oder über eine dem Heap zugewiesene verknüpfte Liste von Frames dargestellt wird).
Um dies zu erreichen, wird eine asymptotische Analyse verwendet:nicht von der Programmausführungszeit, wie man es normalerweise sieht, sondern vom Programm Raumnutzung.Auf diese Weise ist die Speicherplatznutzung einer Heap-zugewiesenen verknüpften Liste im Vergleich zu einem Laufzeit-Aufrufstapel letztendlich asymptotisch äquivalent;man kann also dieses Detail der Programmiersprachenimplementierung ignorieren (ein Detail, das in der Praxis sicherlich von großer Bedeutung ist, aber die Situation ziemlich trüben kann, wenn man versucht festzustellen, ob eine bestimmte Implementierung die Anforderung erfüllt, „property tail rekursiv“ zu sein). )
Das Papier ist aus mehreren Gründen eine sorgfältige Lektüre wert:
Es gibt eine induktive Definition des Schwanzausdrücke Und Schwanzrufe eines Programms.(Eine solche Definition und warum solche Aufrufe wichtig sind, scheint Gegenstand der meisten anderen hier gegebenen Antworten zu sein.)
Hier sind diese Definitionen, nur um einen Vorgeschmack auf den Text zu geben:
Definition 1 Der Schwanzausdrücke eines in Core Scheme geschriebenen Programms werden induktiv wie folgt definiert.
- Der Körper eines Lambda-Ausdrucks ist ein Schwanzausdruck
- Wenn
(if E0 E1 E2)ist ein Schwanzausdruck, dann beidesE1UndE2sind Schwanzausdrücke. - Nichts anderes ist ein Schwanzausdruck.
Definition 2 A Rückruf ist ein Endausdruck, der ein Prozeduraufruf ist.
(Ein rekursiver Tail-Aufruf oder, wie es in der Arbeit heißt, „Self-Tail-Call“ ist ein Sonderfall eines Tail-Calls, bei dem die Prozedur selbst aufgerufen wird.)
Es bietet formale Definitionen für sechs verschiedene „Maschinen“ zur Bewertung des Kernschemas, wobei jede Maschine das gleiche beobachtbare Verhalten aufweist außer für die asymptotisch Raumkomplexitätsklasse, in der sich jeder befindet.
Zum Beispiel, nachdem Definitionen für Maschinen mit jeweils 1 angegeben wurden.Stapelbasierte Speicherverwaltung, 2.Garbage Collection, aber keine Tail Calls, 3.Nach Garbage Collection und Tail Calls geht das Papier weiter mit noch fortschrittlicheren Speicherverwaltungsstrategien wie 4.„evlis tail recursion“, wobei die Umgebung während der Auswertung des letzten Unterausdrucksarguments in einem Tail-Aufruf nicht erhalten bleiben muss, 5.Reduzierung der Umgebung einer Schließung auf Nur die freien Variablen dieses Abschlusses und 6.sogenannte „Safe-for-Space“-Semantik im Sinne von Appel und Shao.
Um zu beweisen, dass die Maschinen tatsächlich zu sechs verschiedenen Raumkomplexitätsklassen gehören, liefert der Artikel für jedes verglichene Maschinenpaar konkrete Beispiele von Programmen, die die asymptotische Raumexplosion auf einer Maschine aufdecken, auf der anderen jedoch nicht.
(Wenn ich jetzt meine Antwort durchlese, bin ich mir nicht sicher, ob es mir tatsächlich gelungen ist, die entscheidenden Punkte zu erfassen Klebepapier.Aber leider kann ich der Ausarbeitung dieser Antwort im Moment nicht mehr Zeit widmen.)
Die rekursive Funktion ist eine Funktion, die ruft von selbst auf
Es ermöglicht Programmierern, effiziente Programme mit a zu schreiben minimale Menge an Code.
Der Nachteil ist, dass sie es können verursachen Endlosschleifen und andere unerwartete Ergebnisse, wenn nicht richtig geschrieben.
Ich werde beides erklären Einfache rekursive Funktion und Tail-rekursive Funktion
Um ein zu schreiben Einfache rekursive Funktion
- Der erste Punkt ist zu berücksichtigen, wann Sie sich dafür entscheiden sollten, aus der Schleife zu kommen, nämlich die IF -Schleife
- Der zweite ist, welchen Prozess wir durchführen müssen, wenn wir unsere eigene Funktion sind
Aus dem gegebenen Beispiel:
public static int fact(int n){
if(n <=1)
return 1;
else
return n * fact(n-1);
}
Aus dem obigen Beispiel
if(n <=1)
return 1;
Ist der entscheidende Faktor, wann die Schleife verlassen werden soll
else
return n * fact(n-1);
Ist die tatsächlich durchzuführende Verarbeitung
Lassen Sie mich die Aufgabe zum leichteren Verständnis einzeln aufteilen.
Mal sehen, was intern passiert, wenn ich renne fact(4)
- Ersetzen von n=4
public static int fact(4){
if(4 <=1)
return 1;
else
return 4 * fact(4-1);
}
If Schleife schlägt fehl, also geht es weiter else Schleife, damit es zurückkehrt 4 * fact(3)
Im Stapelspeicher haben wir
4 * fact(3)Ersetzen Sie n=3
public static int fact(3){
if(3 <=1)
return 1;
else
return 3 * fact(3-1);
}
If Schleife schlägt fehl, also geht es weiter else Schleife
also kehrt es zurück 3 * fact(2)
Denken Sie daran, dass wir „4 * fact(3)“ aufgerufen haben
Die Ausgabe für fact(3) = 3 * fact(2)
Bisher hat der Stapel 4 * fact(3) = 4 * 3 * fact(2)
Im Stapelspeicher haben wir
4 * 3 * fact(2)Ersetzen von n=2
public static int fact(2){
if(2 <=1)
return 1;
else
return 2 * fact(2-1);
}
If Schleife schlägt fehl, also geht es weiter else Schleife
also kehrt es zurück 2 * fact(1)
Denken Sie daran, dass wir angerufen haben 4 * 3 * fact(2)
Die Ausgabe für fact(2) = 2 * fact(1)
Bisher hat der Stapel 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)
Im Stapelspeicher haben wir
4 * 3 * 2 * fact(1)Ersetzen von n=1
public static int fact(1){
if(1 <=1)
return 1;
else
return 1 * fact(1-1);
}
If Schleife ist wahr
also kehrt es zurück 1
Denken Sie daran, dass wir angerufen haben 4 * 3 * 2 * fact(1)
Die Ausgabe für fact(1) = 1
Bisher hat der Stapel 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1
Endlich das Ergebnis von Tatsache(4) = 4 * 3 * 2 * 1 = 24
Der Schwanzrekursion wäre
public static int fact(x, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(x-1, running_total*x);
}
}
- Ersetzen von n=4
public static int fact(4, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(4-1, running_total*4);
}
}
If Schleife schlägt fehl, also geht es weiter else Schleife, damit es zurückkehrt fact(3, 4)
Im Stapelspeicher haben wir
fact(3, 4)Ersetzen Sie n=3
public static int fact(3, running_total=4) {
if (x==1) {
return running_total;
} else {
return fact(3-1, 4*3);
}
}
If Schleife schlägt fehl, also geht es weiter else Schleife
also kehrt es zurück fact(2, 12)
Im Stapelspeicher haben wir
fact(2, 12)Ersetzen von n=2
public static int fact(2, running_total=12) {
if (x==1) {
return running_total;
} else {
return fact(2-1, 12*2);
}
}
If Schleife schlägt fehl, also geht es weiter else Schleife
also kehrt es zurück fact(1, 24)
Im Stapelspeicher haben wir
fact(1, 24)Ersetzen von n=1
public static int fact(1, running_total=24) {
if (x==1) {
return running_total;
} else {
return fact(1-1, 24*1);
}
}
If Schleife ist wahr
also kehrt es zurück running_total
Die Ausgabe für running_total = 24
Endlich das Ergebnis von Tatsache(4,1) = 24
Viele Leute haben die Rekursion hier bereits erklärt.Ich möchte ein paar Gedanken zu einigen Vorteilen der Rekursion aus dem Buch „Concurrency in .NET, Modern patterns of concurrent and parallel programming“ von Riccardo Terrell zitieren:
„Funktionelle Rekursion ist der natürliche Weg, um in FP zu iterieren, da sie die Mutation des Zustands vermeidet.Während jeder Iteration wird stattdessen ein neuer Wert in den Schleifenkonstruktor übergeben (mutiert).Darüber hinaus kann eine rekursive Funktion komponiert werden, die Ihr Programm modularer macht und Möglichkeiten zur Nutzung der Parallelisierung einführt. "
Hier sind auch einige interessante Anmerkungen aus demselben Buch zur Schwanzrekursion:
Die Schwanzaufbereitung ist eine Technik, die eine regelmäßige rekursive Funktion in eine optimierte Version umwandelt, die große Eingänge ohne Risiken und Nebenwirkungen verarbeiten kann.
Beachten Sie, dass der Hauptgrund für einen Schwanzaufruf als Optimierung die Verbesserung der Datenlokalität, des Speicherverbrauchs und der Cache -Nutzung besteht.Durch einen Schwanzaufruf verwendet der Callee den gleichen Stapelraum wie der Anrufer.Dies reduziert den Speicherdruck.Es verbessert den Cache geringfügig, da der gleiche Speicher für nachfolgende Anrufer wiederverwendet wird und im Cache bleiben kann, anstatt eine ältere Cache -Linie zu räumt, um Platz für eine neue Cache -Linie zu schaffen.
A Schwanz rekursiv Funktion ist eine rekursive Funktion, bei der die letzte Operation vor der Rückkehr darin besteht, den rekursiven Funktionsaufruf durchzuführen.Das heißt, der Rückgabewert des rekursiven Funktionsaufrufs wird sofort zurückgegeben.Ihr Code würde beispielsweise so aussehen:
def recursiveFunction(some_params):
# some code here
return recursiveFunction(some_args)
# no code after the return statement
Compiler und Interpreter, die implementieren Tail-Call-Optimierung oder Tail-Call-Beseitigung kann rekursiven Code optimieren, um Stapelüberläufe zu verhindern.Wenn Ihr Compiler oder Interpreter keine Tail-Call-Optimierung implementiert (z. B. der CPython-Interpreter), bietet es keinen zusätzlichen Vorteil, Ihren Code auf diese Weise zu schreiben.
Dies ist beispielsweise eine standardmäßige rekursive Fakultätsfunktion in Python:
def factorial(number):
if number == 1:
# BASE CASE
return 1
else:
# RECURSIVE CASE
# Note that `number *` happens *after* the recursive call.
# This means that this is *not* tail call recursion.
return number * factorial(number - 1)
Und dies ist eine rekursive Tail-Call-Version der Fakultätsfunktion:
def factorial(number, accumulator=1):
if number == 0:
# BASE CASE
return accumulator
else:
# RECURSIVE CASE
# There's no code after the recursive call.
# This is tail call recursion:
return factorial(number - 1, number * accumulator)
print(factorial(5))
(Beachten Sie, dass der CPython-Interpreter zwar keine Tail-Call-Optimierung durchführt, obwohl es sich um Python-Code handelt, sodass eine solche Anordnung Ihres Codes keinen Laufzeitvorteil bringt.)
Möglicherweise müssen Sie Ihren Code etwas unleserlicher machen, um die Tail-Call-Optimierung nutzen zu können, wie im faktoriellen Beispiel gezeigt.(Zum Beispiel ist der Basisfall jetzt etwas unintuitiv und die accumulator (Parameter wird effektiv als eine Art globale Variable verwendet.)
Der Vorteil der Tail-Call-Optimierung besteht jedoch darin, dass sie Stapelüberlauffehler verhindert.(Ich möchte anmerken, dass Sie den gleichen Vorteil erzielen können, wenn Sie einen iterativen Algorithmus anstelle eines rekursiven verwenden.)
Stapelüberläufe werden verursacht, wenn auf den Aufrufstapel zu viele Frame-Objekte übertragen wurden.Ein Frame-Objekt wird auf den Aufrufstapel verschoben, wenn eine Funktion aufgerufen wird, und aus dem Aufrufstapel entfernt, wenn die Funktion zurückkehrt.Frame-Objekte enthalten Informationen wie lokale Variablen und die Codezeile, zu der zurückgekehrt werden soll, wenn die Funktion zurückkehrt.
Wenn Ihre rekursive Funktion zu viele rekursive Aufrufe ohne Rückkehr durchführt, kann der Aufrufstapel sein Rahmenobjektlimit überschreiten.(Die Anzahl variiert je nach Plattform;in Python sind es standardmäßig 1000 Frame-Objekte.) Dies führt zu a Paketüberfluss Fehler.(Hey, daher kommt der Name dieser Website!)
Wenn Ihre rekursive Funktion jedoch als letztes den rekursiven Aufruf durchführt und ihren Rückgabewert zurückgibt, gibt es keinen Grund, das aktuelle Frame-Objekt auf dem Aufrufstapel zu behalten.Wenn es nach dem rekursiven Funktionsaufruf keinen Code gibt, gibt es schließlich keinen Grund, an den lokalen Variablen des aktuellen Frame-Objekts festzuhalten.So können wir das aktuelle Frame-Objekt sofort entfernen, anstatt es auf dem Aufrufstapel zu belassen.Das Endergebnis davon ist, dass Ihr Aufrufstapel nicht größer wird und somit kein Stapelüberlauf möglich ist.
Ein Compiler oder Interpreter muss über eine Funktion zur Tail-Call-Optimierung verfügen, damit er erkennen kann, wann die Tail-Call-Optimierung angewendet werden kann.Selbst dann müssen Sie möglicherweise den Code in Ihrer rekursiven Funktion neu anordnen, um die Tail-Call-Optimierung zu nutzen, und es liegt an Ihnen, ob diese potenzielle Verschlechterung der Lesbarkeit die Optimierung wert ist.
Die Tail-Rekursion ist im Vergleich zur normalen Rekursion ziemlich schnell.Dies ist schnell, da die Ausgabe des Ancestor-Aufrufs nicht in den Stapel geschrieben wird, um den Überblick zu behalten.Aber bei der normalen Rekursion wird die Ausgabe aller Vorfahrenaufrufe in den Stapel geschrieben, um den Überblick zu behalten.
