Ich verstehe fast, wie Tail-Rekursion funktioniert und den Unterschied zwischen ihr und einer normalen Rekursion. ich nur verstehe nicht warum es nicht erfordern, dass sich der Stack seine Rücksendeadresse merkt.
// tail recursion
int fac_times (int n, int acc) {
if (n == 0) return acc;
else return fac_times(n - 1, acc * n);
}
int factorial (int n) {
return fac_times (n, 1);
}
// normal recursion
int factorial (int n) {
if (n == 0) return 1;
else return n * factorial(n - 1);
}
Es gibt nichts zu tun, nachdem eine Funktion selbst in einer Tail-Rekursionsfunktion aufgerufen wurde, aber es macht keinen Sinn für mich.
Schwanzrekursion ist “normale” Rekursion. Es bedeutet nur, dass die Rekursion am Ende der Funktion erfolgt.
– Peter Becker
20. März 2013 um 11:27 Uhr
… Aber es kann auf der IL-Ebene anders implementiert werden als die normale Rekursion, wodurch die Stack-Tiefe reduziert wird.
– KeithS
20. März 2013 um 14:17 Uhr
Übrigens kann gcc hier eine Endrekursionseliminierung für das “normale” Beispiel durchführen.
– dmckee — Ex-Moderator-Kätzchen
20. März 2013 um 16:58 Uhr
@Geek – Ich bin ein C # -Entwickler, also ist meine “Assemblersprache” MSIL oder nur IL. Ersetzen Sie für C/C++ IL durch ASM.
– KeithS
27. März 2013 um 14:20 Uhr
@ShannonSeverance Ich habe festgestellt, dass gcc dies durch die einfache Untersuchung des ausgegebenen Assemblercodes mit ohne tut -O3. Der Link bezieht sich auf eine frühere Diskussion, die einen sehr ähnlichen Bereich abdeckt und erörtert, was zur Implementierung dieser Optimierung erforderlich ist.
– dmckee — Ex-Moderator-Kätzchen
27. März 2013 um 23:42 Uhr
Der Compiler ist einfach in der Lage, dies zu transformieren
int fac_times (int n, int acc) {
if (n == 0) return acc;
else return fac_times(n - 1, acc * n);
}
in so etwas:
int fac_times (int n, int acc) {
label:
if (n == 0) return acc;
acc *= n--;
goto label;
}
@Mr.32 Ich verstehe deine Frage nicht. Ich habe die Funktion in eine äquivalente umgewandelt, aber ohne explizite Rekursion (dh ohne explizite Funktionsaufrufe). Wenn Sie die Logik in etwas Nicht-Äquivalentes ändern, können Sie die Funktion in einigen oder allen Fällen tatsächlich für immer schleifen.
– Alexey Frunze
20. März 2013 um 9:30 Uhr
Tails-Rekursion ist also effektiv nur durch Compiler optimieren? Und ansonsten wäre es in Bezug auf den Stapelspeicher dasselbe wie eine normale Rekursion?
– Alan Coromano
20. März 2013 um 9:48 Uhr
Ja. Wenn der Compiler die Rekursion nicht auf eine Schleife reduzieren kann, bleiben Sie bei der Rekursion hängen. Alles oder nichts.
– Alexey Frunze
20. März 2013 um 9:57 Uhr
@AlanDert: richtig. Sie können die Tail-Rekursion auch als Sonderfall der “Tail-Call-Optimierung” betrachten, speziell, weil der Tail-Aufruf zufällig dieselbe Funktion hat. Im Allgemeinen kann jeder Tail-Aufruf (mit den gleichen Anforderungen an „keine Arbeit mehr zu tun“ wie bei der Tail-Rekursion und bei denen der Rückgabewert des Tail-Aufrufs direkt zurückgegeben wird) optimiert werden, wenn der Compiler den Aufruf in a vornehmen kann Weise, die die Rücksprungadresse der aufgerufenen Funktion so einrichtet, dass sie die Rücksprungadresse der Funktion ist, die den Tail-Aufruf durchführt, anstelle der Adresse, von der der Tail-Aufruf getätigt wurde.
– Steve Jessop
20. März 2013 um 9:59 Uhr
@AlanDert in C ist dies nur eine Optimierung, die von keinem Standard erzwungen wird, daher sollte portabler Code nicht davon abhängen. Aber es gibt Sprachen (Schema ist ein Beispiel), in denen die Endrekursionsoptimierung vom Standard erzwungen wird, sodass Sie sich keine Sorgen machen müssen, dass es in einigen Umgebungen zu einem Stapelüberlauf kommt.
– Jan Wröbel
27. März 2013 um 10:02 Uhr
Lindydancer
Sie fragen, warum “es keinen Stapel benötigt, um sich an seine Absenderadresse zu erinnern”.
Ich würde das gerne umdrehen. Es tut Verwenden Sie den Stack, um sich die Absenderadresse zu merken. Der Trick besteht darin, dass die Funktion, in der die Tail-Rekursion auftritt, ihre eigene Rücksprungadresse auf dem Stapel hat, und wenn sie zur aufgerufenen Funktion springt, behandelt sie diese als ihre eigene Rücksprungadresse.
Konkret ohne Tail-Call-Optimierung:
f: ...
CALL g
RET
g:
...
RET
In diesem Fall wann g aufgerufen wird, sieht der Stack folgendermaßen aus:
SP -> Return address of "g"
Return address of "f"
Auf der anderen Seite mit Tail-Call-Optimierung:
f: ...
JUMP g
g:
...
RET
In diesem Fall wann g aufgerufen wird, sieht der Stack folgendermaßen aus:
SP -> Return address of "f"
Ganz klar, wann g zurückkehrt, wird es an den Ort zurückkehren, wo f wurde von angerufen.
BEARBEITEN: Das obige Beispiel verwendet den Fall, in dem eine Funktion eine andere Funktion aufruft. Der Mechanismus ist identisch, wenn die Funktion sich selbst aufruft.
Dies ist eine viel bessere Antwort als die anderen Antworten. Der Compiler hat höchstwahrscheinlich keinen magischen Spezialfall zum Konvertieren von End-rekursivem Code. Es führt nur eine normale Last-Call-Optimierung durch, die zufällig zu derselben Funktion geht.
– Kunst
20. März 2013 um 12:10 Uhr
Endrekursion kann normalerweise vom Compiler in eine Schleife umgewandelt werden, insbesondere wenn Akkumulatoren verwendet werden.
// tail recursion
int fac_times (int n, int acc = 1) {
if (n == 0) return acc;
else return fac_times(n - 1, acc * n);
}
würde zu so etwas kompilieren
// accumulator
int fac_times (int n) {
int acc = 1;
while (n > 0) {
acc *= n;
n -= 1;
}
return acc;
}
Nicht so schlau wie Alexeys Umsetzung … und ja, das ist ein Kompliment.
– Matthias M.
20. März 2013 um 9:38 Uhr
Eigentlich sieht das Ergebnis einfacher aus, aber ich denke, der Code zum Implementieren dieser Transformation wäre VIEL “cleverer” als entweder label/goto oder nur die Eliminierung von Tail-Calls (siehe Antwort von Lindydancer).
– Phob
22. März 2013 um 6:28 Uhr
Wenn das alles Schwanzrekursion ist, warum regen sich die Leute dann so darüber auf? Ich sehe niemanden, der sich für While-Schleifen begeistert.
– Buh Buh
24. November 2013 um 17:54 Uhr
@BuhBuh: Dies hat keinen Stapelüberlauf und vermeidet das Stapeln von Parametern. Für eine enge Schleife wie diese kann es einen großen Unterschied machen. Ansonsten sollten die Leute nicht aufgeregt sein.
– Muhende Ente
14. November 2014 um 1:26 Uhr
Lukas Ribeiro
Es gibt zwei Elemente, die in einer rekursiven Funktion vorhanden sein müssen:
Der rekursive Aufruf
Ein Ort, um die Rückgabewerte zu zählen.
Eine “normale” rekursive Funktion hält (2) im Stapelrahmen.
Die Rückgabewerte in regulären rekursiven Funktionen bestehen aus zwei Arten von Werten:
Andere Rückgabewerte
Ergebnis der Berechnung der eigenen Funktion
Schauen wir uns dein Beispiel an:
int factorial (int n) {
if (n == 0) return 1;
else return n * factorial(n - 1);
}
Der Rahmen f(5) “speichert” zum Beispiel das Ergebnis seiner eigenen Berechnung (5) und den Wert von f(4). Wenn ich factorial(5) aufrufe, kurz bevor die Stack-Aufrufe zusammenbrechen, habe ich:
Beachten Sie, dass jeder Stapel neben den von mir erwähnten Werten den gesamten Umfang der Funktion speichert. Die Speichernutzung für eine rekursive Funktion f ist also O(x), wobei x die Anzahl der rekursiven Aufrufe ist, die ich machen muss. Wenn ich also 1 KB RAM benötige, um Fakultät (1) oder Fakultät (2) zu berechnen, brauche ich ~ 100 KB, um Fakultät (100) zu berechnen, und so weiter.
Eine Tail Recursive-Funktion fügt (2) in ihre Argumente ein.
In einer Tail-Rekursion übergebe ich das Ergebnis der Teilberechnungen in jedem rekursiven Frame mithilfe von Parametern an den nächsten. Sehen wir uns unser faktorielles Beispiel Tail Recursive an:
int factorial (int n) {
int helper(int num, int accumulated)
{
if num == 0 return accumulated
else return helper(num - 1, accumulated*num)
}
return helper(n, 1)
}
Sehen Sie die Unterschiede? Bei “normalen” rekursiven Aufrufen bilden die Rückgabefunktionen rekursiv den Endwert. In Tail Recursion verweisen sie nur auf den Basisfall (zuletzt ausgewerteter). Wir nennen Akkumulator das Argument, das die älteren Werte verfolgt.
Rekursionsvorlagen
Die reguläre rekursive Funktion lautet wie folgt:
type regular(n)
base_case
computation
return (result of computation) combined with (regular(n towards base case))
Um es in eine Tail-Rekursion umzuwandeln, gehen wir wie folgt vor:
Führen Sie eine Hilfsfunktion ein, die den Akkumulator trägt
Führen Sie die Hilfsfunktion innerhalb der Hauptfunktion aus, wobei der Akkumulator auf den Basisfall eingestellt ist.
Aussehen:
type tail(n):
type helper(n, accumulator):
if n == base case
return accumulator
computation
accumulator = computation combined with accumulator
return helper(n towards base case, accumulator)
helper(n, base case)
Sieh den Unterschied?
Tail-Call-Optimierung
Da auf den Non-Border-Cases der Tail-Call-Stacks kein Zustand gespeichert wird, sind sie nicht so wichtig. Einige Sprachen/Interpreter ersetzen dann den alten Stack durch den neuen. Ohne Stack-Frames, die die Anzahl der Aufrufe einschränken, die Tail Calls verhalten sich wie eine for-Schleife in diesen Fällen.
Es liegt an Ihrem Compiler, es zu optimieren, oder nein.
Khaled.K
Hier ist ein einfaches Beispiel, das zeigt, wie rekursive Funktionen funktionieren:
long f (long n)
{
if (n == 0) // have we reached the bottom of the ocean ?
return 0;
// code executed in the descendence
return f(n-1) + 1; // recurrence
// code executed in the ascendence
}
Endrekursion ist eine einfache rekursive Funktion, bei der die Rekursion am Ende der Funktion ausgeführt wird, sodass kein Code aufsteigend ausgeführt wird, was den meisten Compilern von höheren Programmiersprachen hilft, das zu tun, was als bekannt ist Tail-Rekursionsoptimierunghat auch eine komplexere Optimierung, die als bekannt ist Endrekursion modulo
Nursnaaz
Die rekursive Funktion ist eine Funktion, die ruft von selbst an
Es ermöglicht Programmierern, effiziente Programme mit a zu schreiben minimale Menge an Code.
Der Nachteil ist, dass sie es können Endlosschleifen verursachen und andere unerwartete Ergebnisse, wenn nicht richtig geschrieben.
Ich werde beides erklären Simple Recursive-Funktion und Tail Recursive-Funktion
Um a zu schreiben Einfache rekursive Funktion
Der erste zu berücksichtigende Punkt ist, wann Sie sich entscheiden sollten, die Schleife zu verlassen, die die if-Schleife ist
Die zweite ist, welcher Prozess zu tun ist, 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 obigem Beispiel
if(n <=1)
return 1;
Ist der entscheidende Faktor, wann die Schleife verlassen wird
else
return n * fact(n-1);
Soll die eigentliche Verarbeitung erfolgen
Lassen Sie mich die Aufgabe einzeln aufschlüsseln, um sie leichter zu verstehen.
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 zu else Schleife, damit es zurückkehrt 4 * fact(3)
Im Stapelspeicher haben wir 4 * fact(3)
Ersetzen von 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 zu 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 Stack 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 zu 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 Stack 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 Stack 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1
Endlich das Ergebnis von Tatsache(4) = 4 * 3 * 2 * 1 = 24
Das 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 zu else Schleife, damit es zurückkehrt fact(3, 4)
Im Stapelspeicher haben wir fact(3, 4)
Ersetzen von 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 zu 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 zu 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
iammilind
Meine Antwort ist eher eine Vermutung, da die Rekursion etwas mit der internen Implementierung zu tun hat.
Bei der Schwanzrekursion wird die rekursive Funktion am Ende derselben Funktion aufgerufen. Wahrscheinlich kann der Compiler auf folgende Weise optimieren:
Lassen Sie die laufende Funktion ablaufen (d. h. der verwendete Stack wird abgerufen)
Speichern Sie die Variablen, die als Argumente für die Funktion verwendet werden sollen, in einem temporären Speicher
Rufen Sie danach die Funktion erneut mit dem zwischengespeicherten Argument auf
Wie Sie sehen können, beenden wir die ursprüngliche Funktion vor der nächsten Iteration derselben Funktion, sodass wir den Stapel nicht wirklich “benutzen”.
Aber ich glaube, wenn Destruktoren innerhalb der Funktion aufgerufen werden müssen, dann trifft diese Optimierung möglicherweise nicht zu.
14229500cookie-checkWie genau funktioniert die Schwanzrekursion?yes
Schwanzrekursion ist “normale” Rekursion. Es bedeutet nur, dass die Rekursion am Ende der Funktion erfolgt.
– Peter Becker
20. März 2013 um 11:27 Uhr
… Aber es kann auf der IL-Ebene anders implementiert werden als die normale Rekursion, wodurch die Stack-Tiefe reduziert wird.
– KeithS
20. März 2013 um 14:17 Uhr
Übrigens kann gcc hier eine Endrekursionseliminierung für das “normale” Beispiel durchführen.
– dmckee — Ex-Moderator-Kätzchen
20. März 2013 um 16:58 Uhr
@Geek – Ich bin ein C # -Entwickler, also ist meine “Assemblersprache” MSIL oder nur IL. Ersetzen Sie für C/C++ IL durch ASM.
– KeithS
27. März 2013 um 14:20 Uhr
@ShannonSeverance Ich habe festgestellt, dass gcc dies durch die einfache Untersuchung des ausgegebenen Assemblercodes mit ohne tut
-O3
. Der Link bezieht sich auf eine frühere Diskussion, die einen sehr ähnlichen Bereich abdeckt und erörtert, was zur Implementierung dieser Optimierung erforderlich ist.– dmckee — Ex-Moderator-Kätzchen
27. März 2013 um 23:42 Uhr