Was ist Tail-Rekursion?

Question

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

Answer 1

Es gibt zwei grundlegende Arten von Rekursionen: Kopf-Rekursion et Schwanzrekursion.

Unter Kopf-Rekursion macht eine Funktion ihren rekursiven Aufruf und dann führt eine Funktion weitere Berechnungen durch, vielleicht unter Verwendung des Ergebnisses der rekursiven Aufrufs verwenden.

Dans un Schwanz rekursiv Funktion werden alle Berechnungen zuerst durchgeführt und der rekursive Aufruf ist das letzte, was passiert.

Entnommen aus ce supergeiler Beitrag. Bitte denken Sie daran, ihn zu lesen.

Answer 2

Rekursion bedeutet, dass eine Funktion sich selbst aufruft. Zum Beispiel:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

Tail-Rekursion bezeichnet die Rekursion, die die Funktion abschließt:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

Das letzte, was eine Funktion ohne Ende (im Scheme-Jargon: Prozedur) tut, ist, sich selbst aufzurufen. Ein anderes (nützlicheres) Beispiel ist:

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

In der Hilfsprozedur ist das LETZTE, was sie tut, wenn links nicht null ist, sich selbst aufzurufen (NACH cons something und cdr something). Das ist im Grunde die Art und Weise, wie man eine Liste abbildet.

Die Tail-Rekursion hat den großen Vorteil, dass der Interpreter (oder Compiler, abhängig von der Sprache und dem Hersteller) sie optimieren und in etwas umwandeln kann, das einer while-Schleife entspricht. In der Tat werden in der Scheme-Tradition die meisten "for"- und "while"-Schleifen in einer tail-recursion Weise ausgeführt (es gibt kein for und while, soweit ich weiß).

Answer 3

Die Rekursion wurde hier schon von vielen Leuten erklärt. Ich möchte ein paar Gedanken über einige Vorteile der Rekursion aus dem Buch "Concurrency in .NET, Modern patterns of concurrent and parallel programming" von Riccardo Terrell zitieren:

"Die funktionale Rekursion ist der natürliche Weg, um in FP zu iterieren, weil sie die Mutation des Zustands vermeidet. Bei jeder Iteration wird ein neuer Wert an den Schleifenkonstruktor übergeben, der dann aktualisiert (mutiert) wird. Unter Außerdem kann eine rekursive Funktion zusammengesetzt werden, was Ihr Programm modularer gestalten und Möglichkeiten zur Nutzung von Parallelisierung."

Hier sind auch einige interessante Hinweise aus demselben Buch über Tail-Rekursion:

Tail-Call-Rekursion ist eine Technik, die eine reguläre rekursive Funktion in eine optimierte Version umwandelt, die große Eingaben ohne Risiken und Nebeneffekte.

HINWEIS Der Hauptgrund für einen Tail-Call als Optimierung ist, dass Datenlokalisierung, Speichernutzung und Cache-Nutzung zu verbessern. Durch einen Tail-Call Aufruf verwendet der Aufrufer denselben Stack-Speicherplatz wie der Aufrufer. Dies reduziert Speicherdruck. Der Cache wird geringfügig verbessert, da derselbe Speicher für nachfolgende Aufrufer wiederverwendet wird und im Cache verbleiben kann, anstatt eine ältere Cache-Zeile zu verdrängen, um Platz für eine neue Cache-Zeile zu schaffen Zeile zu schaffen.

Answer 4

Auf diese Frage gibt es viele gute Antworten... aber ich kann nicht anders, als mich mit einer alternativen Sichtweise zur Definition von "Tail-Rekursion" oder zumindest "richtiger Tail-Rekursion" einzuschalten. Nämlich: sollte man sie als eine Eigenschaft eines bestimmten Ausdrucks in einem Programm betrachten? Oder sollte man sie als eine Eigenschaft eines Implementierung einer Programmiersprache ?

Mehr über die letztgenannte Ansicht finden Sie in einem klassischen Papier von Will Clinger, "Proper Tail Recursion and Space Efficiency" (PLDI 1998), in dem "Proper Tail Recursion" als Eigenschaft einer Programmiersprachenimplementierung definiert wird. Die Definition ist so aufgebaut, dass Implementierungsdetails ignoriert werden können (z. B. ob der Aufrufstapel tatsächlich durch den Laufzeitstapel oder durch eine auf dem Heap zugewiesene verknüpfte Liste von Frames dargestellt wird).

Um dies zu erreichen, wird eine asymptotische Analyse verwendet: nicht der Programmausführungszeit, wie man sie üblicherweise sieht, sondern vielmehr der Programm Raumnutzung . Auf diese Weise ist der Platzbedarf einer verknüpften Liste auf dem Heap im Vergleich zu einem Aufrufstapel zur Laufzeit asymptotisch äquivalent, so dass man dieses Detail der Programmiersprachenimplementierung ignorieren kann (ein Detail, das in der Praxis sicherlich eine große Rolle spielt, aber das Wasser ziemlich verwirren kann, wenn man versucht festzustellen, ob eine bestimmte Implementierung die Anforderung erfüllt, "Property Tail Recursive" zu sein)

Das Papier ist aus einer Reihe von Gründen eine sorgfältige Untersuchung wert:

• Sie enthält eine induktive Definition des Begriffs Schwanzausdrücke et Heckanrufe eines Programms. (Eine solche Definition und die Frage, warum solche Aufrufe wichtig sind, scheint das Thema der meisten anderen hier gegebenen Antworten zu sein).

  Hier sind diese Definitionen, nur um einen Eindruck vom Text zu vermitteln:

  Definition 1 Die Schwanzausdrücke eines in Core Scheme geschriebenen Programms sind induktiv wie folgt definiert.

  1. Der Körper eines Lambda-Ausdrucks ist ein Schwanzausdruck
  2. Wenn (if E0 E1 E2) ein Schwanzausdruck ist, dann sind sowohl E1 et E2 sind Schwanzausdrücke.
  3. Nichts anderes ist ein Schwanzausdruck.

  Definition 2 A Heckruf ist ein Schwanzausdruck, der ein Prozeduraufruf ist.

(ein rekursiver Tail-Aufruf oder, wie es in dem Papier heißt, "self-tail call" ist ein Spezialfall eines Tail-Aufrufs, bei dem die Prozedur selbst aufgerufen wird).

• Es bietet formale Definitionen für sechs verschiedene "Maschinen" zur Auswertung von Core Scheme, wobei jede Maschine das gleiche beobachtbare Verhalten aufweist außer für die asymptotisch Raumkomplexitätsklasse, in der sich jeder befindet.

  Nachdem beispielsweise Definitionen für Maschinen mit 1. stapelbasierter Speicherverwaltung, 2. Garbage Collection, aber ohne Tail Calls, 3. Garbage Collection und Tail Calls gegeben wurden, fährt das Papier mit noch fortgeschritteneren Speicherverwaltungsstrategien fort, wie 4. "evlis tail recursion", bei der die Umgebung bei der Auswertung des letzten Unterausdrucks in einem Tail Call nicht erhalten bleiben muss, 5. die Reduzierung der Umgebung einer Closure auf nur die freien Variablen dieses Abschlusses und 6. die so genannte "Safe-for-Space"-Semantik, wie sie von Appel und Shao .

• Um zu beweisen, dass die Maschinen tatsächlich sechs verschiedenen Raumkomplexitätsklassen angehören, enthält das Papier für jedes zu vergleichende Maschinenpaar konkrete Beispiele für Programme, die auf einer Maschine asymptotische Raumvergrößerung zeigen, auf der anderen aber nicht.

---

(Wenn ich mir meine Antwort jetzt durchlese, bin ich mir nicht sicher, ob es mir gelungen ist, die entscheidenden Punkte der Frage zu erfassen. Clinger Papier . Aber leider kann ich im Moment nicht mehr Zeit für die Ausarbeitung dieser Antwort aufwenden).

Answer 5

Es handelt sich um eine besondere Form der Rekursion, bei der die letzte Operation einer Funktion ein rekursiver Aufruf ist. Die Rekursion kann optimiert werden, indem der Aufruf im aktuellen Stapelrahmen ausgeführt und das Ergebnis zurückgegeben wird, anstatt einen neuen Stapelrahmen zu erstellen.

Eine rekursive Funktion ist tail-rekursiv, wenn der rekursive Aufruf das letzte ist, was von der Funktion ausgeführt wird. Zum Beispiel ist die folgende C++-Funktion print() tail-rekursiv.

Ein Beispiel für eine rekursive Schwanzfunktion

    void print(int n) 
{ 
if (n < 0)  return; 
cout << " " << n; 
print(n-1);} 

// The last executed statement is recursive call 

Die tail-rekursiven Funktionen werden als besser angesehen als nicht tail-rekursive Funktionen, da die Tail-Rekursion vom Compiler optimiert werden kann. Die Idee, die von Compilern zur Optimierung von Tail-Recursive-Funktionen verwendet wird, ist einfach: Da der rekursive Aufruf die letzte Anweisung ist, gibt es in der aktuellen Funktion nichts mehr zu tun, so dass die Speicherung des Stack-Frames der aktuellen Funktion sinnlos ist.