Was ist Tail-Rekursion?

Question

Als ich anfing, Lisp zu lernen, stieß ich auf den Begriff tail-recursive . Was bedeutet das genau?

Answer 1

Hier ein kurzer Codeausschnitt zum Vergleich zweier Funktionen. Die erste ist eine herkömmliche Rekursion zur Ermittlung der Fakultät einer gegebenen Zahl. Die zweite verwendet die Schwanzrekursion.

Sehr einfach und intuitiv zu verstehen.

Ob eine rekursive Funktion ein Tail-Recursive ist, kann man leicht daran erkennen, dass sie im Basisfall einen konkreten Wert zurückgibt. Das bedeutet, dass sie nicht 1 oder wahr oder etwas Ähnliches zurückgibt. Sie wird höchstwahrscheinlich eine Variante eines der Methodenparameter zurückgeben.

Eine andere Möglichkeit ist, zu erkennen, ob der rekursive Aufruf frei von jeglicher Addition, Arithmetik, Modifikation usw. ist. Das heißt, es ist nichts anderes als ein reiner rekursiver Aufruf.

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

Answer 2

Die rekursive Funktion ist eine Funktion, die ruft von sich aus

Es erlaubt Programmierern, effiziente Programme zu schreiben, indem sie eine minimale Menge an Code .

Der Nachteil ist, dass sie Endlosschleifen verursachen und andere unerwartete Ergebnisse, wenn nicht richtig geschrieben .

Ich werde beides erklären Einfache rekursive Funktion und rekursive Funktion am Ende

Zum Schreiben einer Einfache rekursive Funktion

1. Der erste Punkt, den Sie bedenken sollten, ist, wann Sie sich für einen Ausstieg entscheiden sollten aus der Schleife, der if-Schleife
2. Die zweite Frage 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 wird

else 
     return n * fact(n-1);

Ist die eigentliche Verarbeitung durchzuführen

Zum besseren Verständnis möchte ich die Aufgaben einzeln aufschlüsseln.

Wir wollen sehen, was intern passiert, wenn ich fact(4)

1. Substitution von n=4

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

If Schleife scheitert, also geht es weiter zu else Schleife und gibt daher 4 * fact(3)

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

   Substitution von n=3

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

If Schleife scheitert, also geht es weiter zu else Schleife

und liefert somit 3 * fact(2)

Erinnern Sie sich, dass wir ```4 * Fakt(3)`` genannt haben.

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

Bislang hat der Stapel 4 * fact(3) = 4 * 3 * fact(2)

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

   Substitution von n=2

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

If Schleife scheitert, also geht es weiter zu else Schleife

und liefert somit 2 * fact(1)

Erinnern Sie sich, wir haben 4 * 3 * fact(2)

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

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

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

   Substituiert man n=1

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

If Schleife ist wahr

und liefert somit 1

Erinnern Sie sich, wir haben 4 * 3 * 2 * fact(1)

Die Ausgabe für fact(1) = 1

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

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

Le site 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. Substitution 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 scheitert, also geht es weiter zu else Schleife und gibt daher fact(3, 4)

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

   Substitution 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 scheitert, also geht es weiter zu else Schleife

und liefert somit fact(2, 12)

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

   Substitution 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 scheitert, also geht es weiter zu else Schleife

und liefert somit fact(1, 24)

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

   Substituiert man 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

und liefert somit running_total

Die Ausgabe für running_total = 24

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

Answer 3

Hier ist eine mögliche rekursive Implementierung der Fibonacci-Funktion in Java:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

Dies steht im Gegensatz zu der standardmäßigen rekursiven Implementierung:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

Answer 4

Ich bin kein Lisp-Programmierer, aber ich denke ce wird helfen.

Im Grunde ist es ein Programmierstil, bei dem der rekursive Aufruf das Letzte ist, was Sie tun.

Answer 5

A Schwanz rekursiv Funktion ist eine rekursive Funktion, die als letzte Operation vor der Rückkehr den rekursiven Funktionsaufruf durchführt. Das heißt, der Rückgabewert des rekursiven Funktionsaufrufs wird sofort zurückgegeben. Ihr Code würde zum Beispiel wie folgt aussehen:

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

Compiler und Interpreter, die Folgendes implementieren Optimierung des Heckaufrufs o Eliminierung von Schwanzgesprächen kann rekursiven Code optimieren, um Stapelüberläufe zu verhindern. Wenn Ihr Compiler oder Interpreter keine Tail-Call-Optimierung implementiert (wie z. B. der CPython-Interpreter), hat es keinen zusätzlichen Nutzen, Ihren Code auf diese Weise zu schreiben.

Dies ist zum Beispiel eine standardmäßige rekursive faktorielle Funktion in Python:

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

Dies ist eine rekursive Version der faktoriellen Funktion, die am Ende aufgerufen wird:

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

(Beachten Sie, dass der CPython-Interpreter, obwohl es sich hier um Python-Code handelt, keine Tail-Call-Optimierung durchführt, so dass die Anordnung Ihres Codes auf diese Weise keinen Laufzeitvorteil bringt).

Möglicherweise müssen Sie Ihren Code etwas unleserlicher gestalten, um die Tail-Call-Optimierung zu nutzen, wie im Beispiel der Fakultät gezeigt. (Zum Beispiel ist der Basisfall jetzt etwas unintuitiv, und die accumulator Parameter wird als eine Art globale Variable verwendet).

Der Vorteil der Tail-Call-Optimierung ist jedoch, dass sie Stack-Overflow-Fehler verhindert. (Ich möchte anmerken, dass Sie denselben Vorteil auch durch die Verwendung eines iterativen Algorithmus anstelle eines rekursiven Algorithmus erzielen können).

Stapelüberläufe werden verursacht, wenn zu viele Rahmenobjekte auf den Aufrufstapel geschoben wurden. Ein Rahmenobjekt wird auf den Aufrufstapel geschoben, wenn eine Funktion aufgerufen wird, und vom Aufrufstapel genommen, wenn die Funktion zurückkehrt. Rahmenobjekte enthalten Informationen wie z. B. lokale Variablen und die Codezeile, zu der zurückgekehrt werden soll, wenn die Funktion zurückkehrt.

Wenn Ihre rekursive Funktion zu viele rekursive Aufrufe macht, ohne zurückzukehren, kann der Aufrufstapel seine Rahmenobjektgrenze überschreiten. (Die Anzahl variiert je nach Plattform; in Python liegt sie standardmäßig bei 1000 Frame-Objekten.) Dies verursacht ein Stapelüberlauf Fehler. (Hey, daher kommt ja auch der Name dieser Website!)

Wenn jedoch das Letzte, was Ihre rekursive Funktion tut, der rekursive Aufruf und die Rückgabe des Rückgabewerts ist, dann gibt es keinen Grund, warum sie das aktuelle Frame-Objekt auf dem Aufrufstapel behalten muss. Denn wenn nach dem rekursiven Funktionsaufruf kein Code folgt, gibt es keinen Grund, die lokalen Variablen des aktuellen Frame-Objekts zu behalten. Wir können also das aktuelle Rahmenobjekt sofort loswerden, anstatt es auf dem Aufrufstapel zu behalten. Das Endergebnis ist, dass der Aufrufstapel nicht größer wird und somit kein Stapelüberlauf möglich ist.

Ein Compiler oder Interpreter muss über eine Tail-Call-Optimierung verfügen, damit er erkennen kann, wann die Tail-Call-Optimierung angewendet werden kann. Selbst dann müssen Sie möglicherweise den Code in Ihrer rekursiven Funktion neu anordnen, um die Tail-Call-Optimierung nutzen zu können, und es liegt an Ihnen, ob diese potenzielle Verschlechterung der Lesbarkeit die Optimierung wert ist.