wake-up-neo.net

Wie genau funktioniert die Rekursion des Endes?

Ich verstehe fast, wie die Rekursion des Schwanzes funktioniert und was der Unterschied zu einer normalen Rekursion ist. Ich nur verstehe nicht, warum es nicht erfordert, dass sich der Stack an seine Absenderadresse erinnert.

// 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 ich eine Funktion in einer Tail-Rekursionsfunktion aufgerufen habe, aber es macht für mich keinen Sinn.

calgorithmrecursiontail-recursion
116
Alan Coromano

Der Compiler kann das einfach umwandeln

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;
}
165
Alexey Frunze

Sie fragen, warum "Stapel nicht erforderlich ist, um sich an seine Absenderadresse zu erinnern".

Ich würde das gerne umkehren. Es tut benutzt den Stack, um sich die Absenderadresse zu merken. Der Trick ist, 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 sieht der Stack beim Aufruf von g folgendermaßen aus:

   SP ->  Return address of "g"
          Return address of "f"

Zum anderen mit Tail-Call-Optimierung:

f: ...
   JUMP g
g:
   ...
   RET

In diesem Fall sieht der Stack beim Aufruf von g folgendermaßen aus:

   SP ->  Return address of "f"

Wenn g zurückkehrt, kehrt es eindeutig zu dem Ort zurück, von dem aus f aufgerufen wurde.

EDIT: Im obigen Beispiel wird der Fall verwendet, in dem eine Funktion eine andere Funktion aufruft. Der Mechanismus ist identisch, wenn die Funktion sich selbst aufruft.

56
Lindydancer

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.

Eine "reguläre" rekursive Funktion behält (2) im Stapelrahmen bei.

Die Rückgabewerte in regulären rekursiven Funktionen setzen sich aus zwei Arten von Werten zusammen:

  • 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) anrufe, 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 Stack neben den oben genannten Werten den gesamten Funktionsumfang speichert. Die Speicherbelegung für eine rekursive Funktion f ist also O (x), wobei x die Anzahl der rekursiven Aufrufe ist, die ich tätigen muss. Wenn Sie also 1kb von RAM zur Berechnung von Fakultät (1) oder Fakultät (2) benötigen, brauche ich ~ 100k zur Berechnung von Fakultät (100) und so weiter.

Eine rekursive rekursive Funktion setzt (2) in ihre Argumente.

Bei einer Endrekursion übergebe ich das Ergebnis der Teilberechnungen in jedem rekursiven Rahmen unter Verwendung von Parametern an den nächsten. Schauen wir uns unser faktorielles Beispiel Tail Recursive an:

int Fakultät (int n) { int helfer (int num, int angesammelt) { if num == 0 kumuliert zurückgegeben sonst Rückkehrhelfer (num - 1, akkumulierte * num) } Rückkehrhelfer (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 Return-Funktionen den endgültigen Wert rekursiv zusammen. In Tail Recursion referenzieren sie nur den Basisfall (zuletzt ausgewertet) . Wir nennen Accumulator das Argument, das die älteren Werte verfolgt.

Rekursionsvorlagen

Die reguläre rekursive Funktion sieht folgendermaßen aus:

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

Um es in eine Tail-Rekursion zu verwandeln:

  • Führen Sie eine Hilfsfunktion ein, die den Akkumulator trägt
  • führen Sie die Helper-Funktion innerhalb der Hauptfunktion aus, wobei der Akkumulator auf das Basisgehäuse 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 Nicht-Grenzfall-Fällen der Rückrufstapel kein Zustand gespeichert wird, sind sie nicht so wichtig. Einige Sprachen/Interpreter ersetzen dann den alten Stapel durch den neuen. Wenn also keine Stack-Frames die Anzahl der Aufrufe einschränken, verhalten sich die Tail Calls wie eine for-Schleife in diesen Fällen.

Es liegt an Ihrem Compiler, ihn zu optimieren oder nicht.

11
Lucas Ribeiro

Tail-Rekursion kann normalerweise vom Compiler in eine Schleife umgewandelt werden, insbesondere wenn Akkus 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 so etwas kompilieren

// accumulator
int fac_times (int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n -= 1;
    }
    return acc;
}
11
mepcotterell

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

}

Die Tail-Rekursion ist eine einfache rekursive Funktion, bei der am Ende der Funktion eine Recurrence ausgeführt wird. Daher wird kein Code in absteigender Reihenfolge ausgeführt. Dies hilft den meisten Compilern von Programmiersprachen auf höherer Ebene, die sogenannte Tail Recursion-Optimierung , hat auch eine komplexere Optimierung, die als Tail-Rekursionsmodul bekannt ist.

6
Khaled.K

Die rekursive Funktion ist eine Funktion, die von sich aus 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 nicht richtig geschrieben wird .

Ich werde sowohl die einfache rekursive Funktion als auch die rekursive Schwanzfunktion 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;

Entscheidend ist, wann die Schleife verlassen wird

else 
     return n * fact(n-1);

Ist die eigentliche Bearbeitung durchzuführen?

Lassen Sie mich die Aufgabe zum besseren Verständnis einzeln auflösen.

Mal sehen, was intern passiert, wenn ich fact(4) starte

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

If Schleife schlägt fehl und geht zu else Schleife und gibt 4 * fact(3) zurück

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

Die If - Schleife schlägt fehl und wechselt zur else - Schleife

so gibt es 3 * fact(2) zurück

Denken Sie daran, dass wir "4 * fact (3)" genannt haben

Die Ausgabe für fact(3) = 3 * fact(2)

Bisher hat der Stapel 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);
}

Die If - Schleife schlägt fehl und wechselt zur else - Schleife

so gibt es 2 * fact(1) zurück

Denken Sie daran, wir haben 4 * 3 * fact(2) aufgerufen

Die Ausgabe für fact(2) = 2 * fact(1)

Bisher hat der Stapel 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 gibt es zurück 1

Denken Sie daran, wir haben 4 * 3 * 2 * fact(1) aufgerufen

Die Ausgabe für fact(1) = 1

Bisher hat der Stapel 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Schließlich ist das Ergebnis von fact (4) = 4 * 3 * 2 * 1 = 24

enter image description here

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

If Schleife schlägt fehl und geht zu else Schleife und gibt fact(3, 4) zurück

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

Die If - Schleife schlägt fehl und wechselt zur else - Schleife

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

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

Die If - Schleife schlägt fehl und wechselt zur else - Schleife

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

  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 gibt es zurück running_total

Die Ausgabe für running_total = 24

Schließlich ist das Ergebnis von fact (4,1) = 24

enter image description here

1
Nursnaaz

Der Compiler ist intelligent genug, um die Rekursion von Abschnitten zu verstehen. Wenn von einem rekursiven Aufruf zurückgekehrt wird, gibt es keine ausstehende Operation, und der rekursive Aufruf ist die letzte Anweisung. Er fällt unter die Kategorie der rekursiven Rekursion. __ Compiler führt im Wesentlichen die Optimierung der rekursiven Rekursion aus , Stack-Implementierung entfernen.Consider unter dem 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 einen unter 1 konvertiert.

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

So führt der Compiler die Optimierung der Rekursionsreihenfolge durch.

0
Varunnuevothoughts

Meine Antwort ist eher eine Vermutung, weil 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 aufrollen (d. H., Der verwendete Stapel wird aufgerufen).
  2. Speichern Sie die Variablen, die als Argument für die Funktion verwendet werden sollen, in einem temporären Speicher 
  3. Rufen Sie danach die Funktion erneut mit dem temporär gespeicherten Argument auf

Wie Sie sehen, wickeln wir die ursprüngliche Funktion vor der nächsten Iteration derselben Funktion auf, so dass wir den Stapel nicht wirklich "verwenden". 

Aber ich glaube, wenn Destruktoren innerhalb der Funktion aufgerufen werden sollen, kann diese Optimierung nicht angewendet werden.

0
iammilind