Wie genau funktioniert die Schwanzrekursion?

Lesezeit: 11 Minuten

Benutzeravatar von Alan Coromano
Alan Coromano

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

Benutzeravatar von Lindydancer
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

Benutzeravatar von Lucas Ribeiro
Lukas Ribeiro

Es gibt zwei Elemente, die in einer rekursiven Funktion vorhanden sein müssen:

  1. Der rekursive Aufruf
  2. 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:

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

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

Schauen wir uns die Frames in Factorial (4) an:

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

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.

Benutzeravatar von Khaled.K
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

Benutzeravatar von Nursnaaz
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

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

  1. 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)

  1. 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)

  1. 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)

  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

Geben Sie hier die Bildbeschreibung ein

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);
    }
}

  1. 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)

  1. 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)

  1. 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)

  1. 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

Geben Sie hier die Bildbeschreibung ein

Benutzeravatar von iammilind
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:

  1. Lassen Sie die laufende Funktion ablaufen (d. h. der verwendete Stack wird abgerufen)
  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 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.

1422950cookie-checkWie genau funktioniert die Schwanzrekursion?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy