Was ist Tail-Rekursion?

Question

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

Answer 1

Tail-Rekursion ist das Leben, das Sie gerade führen. Sie recyceln ständig denselben Stack-Frame, immer und immer wieder, weil es keinen Grund oder keine Möglichkeit gibt, zu einem "früheren" Frame zurückzukehren. Die Vergangenheit ist vorbei und kann weggeworfen werden. Sie erhalten einen Frame, der sich immer weiter in die Zukunft bewegt, bis Ihr Prozess unweigerlich stirbt.

_{Die Analogie bricht zusammen, wenn man bedenkt, dass einige Prozesse zusätzliche Frames verwenden könnten, aber immer noch als tail-recursive angesehen werden, wenn der Stack nicht unendlich wächst.}

Answer 2

Die Tail-Rekursion ist im Vergleich zur normalen Rekursion ziemlich schnell. Sie ist schnell, weil die Ausgabe der Vorgängeraufrufe nicht in den Stack geschrieben wird, um den Überblick zu behalten. Aber in der normalen Rekursion werden alle Vorgängeraufrufe in den Stapel geschrieben, um den Überblick zu behalten.

Answer 3

Eine Funktion ist schwanzrekursiv, wenn jeder rekursive Fall aus nur eines Aufrufs der Funktion selbst, möglicherweise mit anderen Argumenten. Oder, Schwanzrekursion ist Rekursion ohne ausstehende Arbeit . Beachten Sie, dass dies ein von der Programmiersprache unabhängiges Konzept ist.

Betrachten Sie die wie folgt definierte Funktion:

g(a, b, n) = a * b^n

Eine mögliche tail-rekursive Formulierung ist:

g(a, b, n) | n is zero = a
           | n is odd  = g(a*b, b,   n-1)
           | otherwise = g(a,   b*b, n/2)

Wenn Sie jede RHS von g(...) die einen rekursiven Fall beinhaltet, werden Sie feststellen, dass der gesamte Körper der RHS ein Aufruf von g(...) y nur das. Diese Definition ist Schwanz rekursiv .

Zum Vergleich könnte eine nicht-schwanzrekursive Formulierung lauten:

g'(a, b, n) = a * f(b, n)
f(b, n) | n is zero = 1
        | n is odd  = f(b, n-1) * b
        | otherwise = f(b, n/2) ^ 2

Jeder rekursive Fall in f(...) hat einige ausstehende Arbeiten die nach dem rekursiven Aufruf erfolgen muss.

Beachten Sie, dass wir beim Übergang von g' a g haben wir uns die Assoziativität zunutze gemacht (und Kommutativität) der Multiplikation. Das ist kein Zufall, und in den meisten Fällen, in denen Sie eine Rekursion in eine Tail-Rekursion umwandeln müssen, werden Sie von solchen Eigenschaften Gebrauch machen: Wenn wir eine Arbeit eifrig erledigen wollen, anstatt sie in der Schwebe zu lassen, müssen wir etwas wie Assoziativität verwenden, um zu beweisen, dass die Antwort dieselbe sein wird.

Rekursive Aufrufe am Ende können mit einem Rückwärtssprung implementiert werden, im Gegensatz zur Verwendung eines Stacks für normale rekursive Aufrufe. Beachten Sie, dass die Erkennung eines Tail-Aufrufs oder das Auslösen eines Rückwärtssprungs in der Regel einfach ist. Allerdings ist es oft schwierig, die Argumente so anzuordnen, dass der Rückwärtssprung möglich ist. Da diese Optimierung nicht kostenlos ist, können Sprachimplementierungen sich dafür entscheiden, diese Optimierung nicht zu implementieren oder ein Opt-In zu verlangen, indem sie rekursive Aufrufe mit einer 'tailcall'-Anweisung markieren und/oder eine höhere Optimierungseinstellung wählen.

Einige Sprachen (z. B. Scheme) erfordern jedoch todo Implementierungen, um tail-rekursive Funktionen zu optimieren, vielleicht sogar alle Aufrufe in tail-Position.

Rückwärtssprünge werden in den meisten imperativen Sprachen in der Regel als (while)-Schleife abstrahiert, und Tail-Rekursion ist, wenn sie zu einem Rückwärtssprung optimiert wird, isomorph zur Schleifenbildung.

Answer 4

• Tail Recursive Function ist eine rekursive Funktion, bei der der rekursive Aufruf der letzte ausgeführte Teil der Funktion ist.

Bei einer normalen rekursiven Funktion haben wir einen Stapel und jedes Mal, wenn wir eine rekursive Funktion innerhalb dieser rekursiven Funktion aufrufen, wird eine weitere Schicht zu unserem Aufrufstapel hinzugefügt. Bei normaler Rekursion Raum: O(n) Schwanzrekursion macht die Raumkomplexität von

O(N)=>O(1)

• Tail-Call-Optimierung bedeutet, dass es möglich ist, eine Funktion von einer anderen Funktion aus aufzurufen, ohne den Aufrufstapel zu vergrößern.

• Wir sollten die Tail-Rekursion in rekursive Lösungen schreiben. Aber bestimmte Sprachen unterstützen die Tail-Rekursion in ihrer Engine, die die Sprache herunterkompiliert, nicht wirklich. BUt keiner der Engines, die js kompilieren, hat tail recursion implementiert. man wird in js nicht O(1) erreichen, weil der Compiler selbst nicht weiß, wie man diese tail recursion implementiert. Ab dem 1. Januar 2020 ist Safari der einzige Browser, der die Tail-Call-Optimierung unterstützt.

• Haskell und Java haben eine Schwanzrekursionsoptimierung

Regelmäßig rekursiv faktoriell

function Factorial(x) {
  //Base case x<=1
  if (x <= 1) {
    return 1;
  } else {
    // x is waiting for the return value of Factorial(x-1)
    // the last thing we do is NOT applying the recursive call
    // after recursive call we still have to multiply.
    return x * Factorial(x - 1);
  }
}

haben wir 4 Aufrufe in unserem Aufrufstapel.

Factorial(4); // waiting in the memory for Factorial(3)
4 * Factorial(3); //  waiting in the memory for Factorial(2)
4 * (3 * Factorial(2)); //  waiting in the memory for Factorial(1)
4 * (3 * (2 * Factorial(1)));
4 * (3 * (2 * 1));

• Wir machen 4 Factorial()-Aufrufe, der Platz ist O(n)
• dies könnte zu Stackoverflow führen

Schwanz Rekursiv Faktoriell

function tailFactorial(x, totalSoFar = 1) {
  //Base Case: x===0. In recursion there must be base case. Otherwise they will never stop
  if (x === 0) {
    return totalSoFar;
  } else {
    // there is nothing waiting for tailFactorial to complete. we are returning another instance of tailFactorial()
    // we are not doing any additional computaion with what we get back from this recursive call
    return tailFactorial(x - 1, totalSoFar * x);
  }
}

• Nach unserem rekursiven Aufruf brauchen wir uns nichts mehr zu merken

Answer 5

Um einige der wichtigsten Unterschiede zwischen Tail-Call-Rekursion und Non-Tail-Call-Rekursion zu verstehen, können wir die .NET-Implementierungen dieser Techniken untersuchen.

Hier ist ein Artikel mit einigen Beispielen in C#, F# und C++ \CLI : Abenteuer in Tail-Rekursion in C#, F# und C++ \CLI .

C# ist nicht für Tail-Call-Rekursion optimiert, F# hingegen schon.

Die prinzipiellen Unterschiede betreffen Schleifen vs. Lambda-Kalkül. C# ist auf Schleifen ausgelegt, während F# auf den Prinzipien des Lambda-Kalküls aufbaut. Ein sehr gutes (und kostenloses) Buch über die Prinzipien von Lambda calculus finden Sie unter Structure and Interpretation of Computer Programs, von Abelson, Sussman und Sussman .

Zum Thema Schwanzaufrufe in F# gibt es einen sehr guten einführenden Artikel, siehe Ausführliche Einführung in Tail Calls in F# . Schließlich finden Sie hier einen Artikel, der den Unterschied zwischen Non-Tail-Rekursion und Tail-Call-Rekursion (in F#) behandelt: Tail-Rekursion vs. Non-Tail-Rekursion in Fis .

Wenn Sie etwas über die Designunterschiede der Tail-Call-Rekursion zwischen C# und F# lesen möchten, lesen Sie Erzeugen von Tail-Call Opcode in C# und F# .

Wenn Sie wissen möchten, welche Bedingungen den C#-Compiler daran hindern, Tail-Call-Optimierungen durchzuführen, lesen Sie diesen Artikel: JIT CLR Tail-Call-Bedingungen .