Ich verstehe fast, wie die Schwanzrekursion funktioniert und welchen Unterschied sie zu einer normalen Rekursion hat. Ich verstehe nur nicht, warum es keinen Stapel erfordert, um sich seine Absenderadresse zu merken.
// 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 Schwanzrekursionsfunktion aufgerufen wurde, aber es macht für mich keinen Sinn.
c
algorithm
recursion
tail-recursion
Alan Coromano
quelle
quelle
-O3
. Der Link ist für eine frühere Diskussion gedacht, die sehr ähnliche Themen abdeckt und erläutert, was zur Implementierung dieser Optimierung erforderlich ist.Antworten:
Der Compiler kann dies einfach transformieren
in so etwas:
quelle
Sie fragen, warum "kein Stapel erforderlich ist, um sich an seine Absenderadresse zu erinnern".
Ich würde das gerne umdrehen. Es tut den Stapel verwenden , um die Absenderadresse zu erinnern. Der Trick besteht darin, dass die Funktion, in der die Schwanzrekursion auftritt, eine eigene Rücksprungadresse auf dem Stapel hat. Wenn sie zur aufgerufenen Funktion springt, wird diese als ihre eigene Rücksprungadresse behandelt.
Konkret ohne Tail-Call-Optimierung:
In diesem Fall
g
sieht der Stapel beim Aufruf folgendermaßen aus:Auf der anderen Seite mit Tail-Call-Optimierung:
In diesem Fall
g
sieht der Stapel beim Aufruf folgendermaßen aus:Wenn Sie
g
zurückkehren, wird es eindeutig an den Ort zurückkehren, von dem aus Sief
angerufen wurden.BEARBEITEN : Im obigen Beispiel wird der Fall verwendet, in dem eine Funktion eine andere Funktion aufruft. Der Mechanismus ist identisch, wenn sich die Funktion selbst aufruft.
quelle
Die Schwanzrekursion kann normalerweise vom Compiler in eine Schleife umgewandelt werden, insbesondere wenn Akkumulatoren verwendet werden.
würde zu so etwas kompilieren
quelle
In einer rekursiven Funktion müssen zwei Elemente vorhanden sein:
Eine "reguläre" rekursive Funktion hält (2) im Stapelrahmen.
Die Rückgabewerte in der regulären rekursiven Funktion bestehen aus zwei Arten von Werten:
Schauen wir uns Ihr Beispiel an:
Der Rahmen f (5) "speichert" beispielsweise das Ergebnis seiner eigenen Berechnung (5) und den Wert von f (4). Wenn ich Fakultät (5) aufrufe, kurz bevor die Stapelaufrufe zusammenbrechen, habe ich:
Beachten Sie, dass jeder Stapel neben den genannten Werten den gesamten Funktionsumfang speichert. Die Speichernutzung für eine rekursive Funktion f ist also O (x), wobei x die Anzahl der rekursiven Aufrufe ist, die ich ausführen 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 rekursive Schwanzfunktion setzt (2) in ihre Argumente.
Bei einer Schwanzrekursion übergebe ich das Ergebnis der Teilberechnungen in jedem rekursiven Rahmen unter Verwendung von Parametern an den nächsten. Sehen wir uns unser faktorielles Beispiel Tail Recursive an:
int Fakultät (int n) {int Helfer (int num, int akkumuliert) {wenn num == 0 zurück akkumuliert sonst Rückgabehelfer (num - 1, akkumuliert * num)} Rückkehr Helfer (n, 1)
}
Schauen wir uns die Frames in Fakultät (4) an:
Sehen Sie die Unterschiede? Bei "regulären" rekursiven Aufrufen setzen die Rückgabefunktionen den Endwert rekursiv zusammen. In der Schwanzrekursion verweisen sie nur auf den Basisfall (zuletzt ausgewertet) . Wir nennen Akkumulator das Argument, das die älteren Werte verfolgt.
Rekursionsvorlagen
Die reguläre rekursive Funktion lautet wie folgt:
Um es in eine Schwanzrekursion umzuwandeln, haben wir:
Aussehen:
Sieh den Unterschied?
Tail Call-Optimierung
Da in den Non-Border-Cases der Tail Call-Stapel kein Status gespeichert ist, sind sie nicht so wichtig. Einige Sprachen / Dolmetscher ersetzen dann den alten Stapel durch den neuen. Da die Anzahl der Aufrufe nicht durch Stapelrahmen eingeschränkt wird, verhalten sich die Endaufrufe in diesen Fällen wie eine for-Schleife .
Es liegt an Ihrem Compiler, es zu optimieren, oder nein.
quelle
Hier ist ein einfaches Beispiel, das zeigt, wie rekursive Funktionen funktionieren:
Endrekursion ist eine einfache rekursive Funktion, wo Wiederholung am Ende der Funktion erfolgt, so wird kein Code in ascendence getan, die meisten Compiler von High-Level - Programmiersprachen hilft zu tun , was bekanntlich Endrekursion Optimierung , hat auch eine komplexere Optimierung, bekannt als Tail-Rekursionsmodulo
quelle
Die rekursive Funktion ist eine Funktion, die von selbst aufruft
Es ermöglicht Programmierern, effiziente Programme mit einer minimalen Menge an Code zu schreiben .
Der Nachteil ist, dass sie Endlosschleifen und andere unerwartete Ergebnisse verursachen können, wenn sie nicht richtig geschrieben werden .
Ich werde sowohl die einfache rekursive Funktion als auch die Schwanzrekursive Funktion erklären
Um eine einfache rekursive Funktion zu schreiben
Aus dem gegebenen Beispiel:
Aus dem obigen Beispiel
Ist der entscheidende Faktor, wann die Schleife verlassen werden soll
Ist die eigentliche Verarbeitung durchzuführen
Lassen Sie mich die Aufgabe einzeln aufteilen, um das Verständnis zu erleichtern.
Mal sehen, was intern passiert, wenn ich renne
fact(4)
If
Die Schleife schlägt fehl und geht zurelse
Schleife, sodass sie zurückkehrt4 * fact(3)
Im Stapelspeicher haben wir
4 * fact(3)
Einsetzen von n = 3
If
Die Schleife schlägt fehl und geht zurelse
Schleifeso kehrt es zurück
3 * fact(2)
Denken Sie daran, wir haben `` `4 * fact (3)` `genannt
Die Ausgabe für
fact(3) = 3 * fact(2)
Soweit hat der Stack
4 * fact(3) = 4 * 3 * fact(2)
Im Stapelspeicher haben wir
4 * 3 * fact(2)
Einsetzen von n = 2
If
Die Schleife schlägt fehl und geht zurelse
Schleifeso kehrt es zurück
2 * fact(1)
Denken Sie daran, wir haben angerufen
4 * 3 * fact(2)
Die Ausgabe für
fact(2) = 2 * fact(1)
Soweit hat der Stack
4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)
Im Stapelspeicher haben wir
4 * 3 * 2 * fact(1)
Einsetzen von n = 1
If
Schleife ist wahrso kehrt es zurück
1
Denken Sie daran, wir haben angerufen
4 * 3 * 2 * fact(1)
Die Ausgabe für
fact(1) = 1
Soweit hat der Stack
4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1
Schließlich ist das Ergebnis von Tatsache (4) = 4 · 3 · 2 · 1 = 24
Die Schwanzrekursion wäre
If
Die Schleife schlägt fehl und geht zurelse
Schleife, sodass sie zurückkehrtfact(3, 4)
Im Stapelspeicher haben wir
fact(3, 4)
Einsetzen von n = 3
If
Die Schleife schlägt fehl und geht zurelse
Schleifeso kehrt es zurück
fact(2, 12)
Im Stapelspeicher haben wir
fact(2, 12)
Einsetzen von n = 2
If
Die Schleife schlägt fehl und geht zurelse
Schleifeso kehrt es zurück
fact(1, 24)
Im Stapelspeicher haben wir
fact(1, 24)
Einsetzen von n = 1
If
Schleife ist wahrso kehrt es zurück
running_total
Die Ausgabe für
running_total = 24
Schließlich ist das Ergebnis der Tatsache (4,1) = 24
quelle
Meine Antwort ist eher eine Vermutung, da 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 wie folgt optimieren:
Wie Sie sehen können, wickeln wir die ursprüngliche Funktion vor der nächsten Iteration derselben Funktion ab, sodass wir den Stapel nicht wirklich "verwenden".
Ich glaube jedoch, dass diese Optimierung möglicherweise nicht angewendet wird, wenn innerhalb der Funktion Destruktoren aufgerufen werden müssen.
quelle
Der Compiler ist intelligent genug, um die Schwanzrekursion zu verstehen. Falls bei der Rückkehr von einem rekursiven Aufruf keine Operation ansteht und der rekursive Aufruf die letzte Anweisung ist, fallen Sie unter die Kategorie der Schwanzrekursion. Der Compiler führt im Wesentlichen eine Optimierung der Schwanzrekursion durch und entfernt die Stapelimplementierung. Berücksichtigen Sie den folgenden Code.
Nach der Optimierung wird der obige Code in den folgenden Code konvertiert.
Auf diese Weise führt der Compiler die Optimierung der Schwanzrekursion durch.
quelle