Wie genau funktioniert die Schwanzrekursion?

121

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.

Alan Coromano
quelle
16
Schwanzrekursion ist "normale" Rekursion. Dies bedeutet nur, dass die Rekursion am Ende der Funktion erfolgt.
Pete Becker
7
... Aber es kann auf IL-Ebene anders implementiert werden als bei normaler Rekursion, wodurch die Stapeltiefe verringert wird.
KeithS
2
Übrigens kann gcc hier am "normalen" Beispiel eine Eliminierung der Schwanzrekursion durchführen.
dmckee --- Ex-Moderator Kätzchen
1
@Geek - Ich bin ein C # -Entwickler, daher ist meine "Assemblersprache" MSIL oder nur IL. Ersetzen Sie für C / C ++ IL durch ASM.
KeithS
1
@ShannonSeverance Ich fand heraus, dass gcc dies durch das einfache Hilfsmittel tut, das den ausgegebenen Assembler-Code mit ohne untersucht -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.
dmckee --- Ex-Moderator Kätzchen

Antworten:

169

Der Compiler kann dies einfach 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;
}
Alexey Frunze
quelle
2
@ Mr.32 Ich verstehe deine Frage nicht. Ich habe die Funktion in eine äquivalente konvertiert, jedoch ohne explizite Rekursion (dh ohne explizite Funktionsaufrufe). Wenn Sie die Logik in etwas Nicht-Äquivalentes ändern, können Sie die Funktionsschleife in einigen oder allen Fällen für immer erstellen.
Alexey Frunze
18
Die Rekursion von Schwänzen ist also nur deshalb effektiv , weil der Compiler sie optimiert? Und sonst wäre es das gleiche wie eine normale Rekursion in Bezug auf den Stapelspeicher?
Alan Coromano
34
Ja. Wenn der Compiler die Rekursion nicht auf eine Schleife reduzieren kann, bleibt die Rekursion bestehen. Alles oder nichts.
Alexey Frunze
3
@ AlanDert: richtig. Sie können die Schwanzrekursion auch als Sonderfall der "Schwanzaufrufoptimierung" betrachten, insbesondere weil der Schwanzaufruf zufällig dieselbe Funktion hat. Im Allgemeinen kann jeder Tail-Aufruf (mit den gleichen Anforderungen an "Keine Arbeit mehr" wie für die Tail-Rekursion und bei denen der Rückgabewert des Tail-Aufrufs direkt zurückgegeben wird) optimiert werden, wenn der Compiler den Aufruf in a ausführen kann Methode, mit der die Rücksprungadresse der aufgerufenen Funktion als Rücksprungadresse der Funktion eingerichtet wird, die den Endaufruf ausführt, anstelle der Adresse, von der aus der Rückruf aufgerufen wurde.
Steve Jessop
1
@AlanDert in C Dies ist nur eine Optimierung, die von keinem Standard erzwungen wird, sodass portabler Code nicht davon abhängen sollte. Es gibt jedoch Sprachen (Schema ist ein Beispiel), in denen die Optimierung der Schwanzrekursion durch den Standard erzwungen wird, sodass Sie sich keine Sorgen machen müssen, dass in einigen Umgebungen ein Stapelüberlauf auftritt.
Jan Wrobel
57

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:

f: ...
   CALL g
   RET
g:
   ...
   RET

In diesem Fall gsieht der Stapel beim Aufruf 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 gsieht der Stapel beim Aufruf folgendermaßen aus:

   SP ->  Return address of "f"

Wenn Sie gzurückkehren, wird es eindeutig an den Ort zurückkehren, von dem aus Sie fangerufen 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.

Lindydancer
quelle
8
Dies ist eine viel bessere Antwort als die anderen Antworten. Der Compiler hat höchstwahrscheinlich keinen magischen Sonderfall zum Konvertieren von rekursivem Endcode. Es wird nur eine normale Optimierung des letzten Anrufs durchgeführt, die zufällig zur gleichen Funktion wechselt.
Art
12

Die Schwanzrekursion 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;
}
Mepcotterell
quelle
3
Nicht so clever wie Alexeys Implementierung ... und ja, das ist ein Kompliment.
Matthieu M.
1
Eigentlich sieht das Ergebnis einfacher aus, aber ich denke, der Code zur Implementierung dieser Transformation wäre weitaus "cleverer" als entweder label / goto oder nur die Eliminierung von Tail Calls (siehe Lindydancers Antwort).
Phob
Wenn das alles Schwanzrekursion ist, warum sind die Leute dann so aufgeregt darüber? Ich sehe niemanden, der sich über Loops aufregt.
Buh Buh
@BuhBuh: Dies hat keinen Stackoverflow und vermeidet das Stack-Push / Popping von Parametern. Für eine enge Schleife wie diese kann es einen großen Unterschied machen. Davon abgesehen sollten die Leute nicht aufgeregt sein.
Mooing Duck
11

In einer rekursiven Funktion müssen zwei Elemente vorhanden sein:

  1. Der rekursive Aufruf
  2. Ein Ort, an dem die Rückgabewerte gezählt werden können.

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:

  • Andere Rückgabewerte
  • Ergebnis der eigenen Funktionsberechnung

Schauen wir uns Ihr Beispiel an:

int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

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:

 [Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]

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:

[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]

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:

type regular(n)
    base_case
    computation
    return (result of computation) combined with (regular(n towards base case))

Um es in eine Schwanzrekursion umzuwandeln, haben wir:

  • Führen Sie eine Hilfsfunktion ein, die den Akku trägt
  • Führen Sie die Hilfsfunktion innerhalb der Hauptfunktion aus, wobei der Akku 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 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.

Lucas Ribeiro
quelle
6

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, 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

Khaled.K
quelle
1

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

  1. Der erste zu berücksichtigende Punkt ist, wann Sie sich entscheiden sollten, aus der Schleife herauszukommen, die die if-Schleife ist
  2. Der zweite ist, was 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 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 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)

  1. Einsetzen von n = 4
public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

IfDie Schleife schlägt fehl und geht zur elseSchleife, sodass sie zurückkehrt4 * fact(3)

  1. Im Stapelspeicher haben wir 4 * fact(3)

    Einsetzen von n = 3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

IfDie Schleife schlägt fehl und geht zur elseSchleife

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

  1. Im Stapelspeicher haben wir 4 * 3 * fact(2)

    Einsetzen von n = 2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

IfDie Schleife schlägt fehl und geht zur elseSchleife

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

  1. Im Stapelspeicher haben wir 4 * 3 * 2 * fact(1)

    Einsetzen von n = 1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If Schleife ist wahr

so 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

Geben Sie hier die Bildbeschreibung ein

Die 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);
    }
}
  1. Einsetzen 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);
    }
}

IfDie Schleife schlägt fehl und geht zur elseSchleife, sodass sie zurückkehrtfact(3, 4)

  1. Im Stapelspeicher haben wir fact(3, 4)

    Einsetzen von n = 3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

IfDie Schleife schlägt fehl und geht zur elseSchleife

so kehrt es zurück fact(2, 12)

  1. Im Stapelspeicher haben wir fact(2, 12)

    Einsetzen von n = 2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

IfDie Schleife schlägt fehl und geht zur elseSchleife

so kehrt es zurück fact(1, 24)

  1. Im Stapelspeicher haben wir fact(1, 24)

    Einsetzen 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

so kehrt es zurück running_total

Die Ausgabe für running_total = 24

Schließlich ist das Ergebnis der Tatsache (4,1) = 24

Geben Sie hier die Bildbeschreibung ein

Nursnaaz
quelle
0

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:

  1. Lassen Sie die laufende Funktion auflaufen (dh der verwendete Stapel wird zurückgerufen)
  2. Speichern Sie die Variablen, die als Argumente für die Funktion verwendet werden sollen, in einem temporären Speicher
  3. Rufen Sie danach die Funktion mit dem vorübergehend gespeicherten Argument erneut auf

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.

iammilind
quelle
0

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.

void tail(int i) {
    if(i<=0) return;
    else {
     system.out.print(i+"");
     tail(i-1);
    }
   }

Nach der Optimierung wird der obige Code in den folgenden Code konvertiert.

void tail(int i) {
    blockToJump:{
    if(i<=0) return;
    else {
     system.out.print(i+"");
     i=i-1;
     continue blockToJump;  //jump to the bolckToJump
    }
    }
   }

Auf diese Weise führt der Compiler die Optimierung der Schwanzrekursion durch.

Varunnuevothoughts
quelle