Was ist Tail-Rekursion?

Question

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

Answer 1

In der Jargon-Datei steht Folgendes über die Definition der Tail-Rekursion:

Schwanzrekursion /n./

Falls Sie es noch nicht satt haben, siehe Schwanzrekursion.

Answer 2

Anstatt es mit Worten zu erklären, hier ein Beispiel. Dies ist eine Scheme-Version der faktoriellen Funktion:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

Hier ist eine Version von factorial, die tail-rekursiv ist:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

Sie werden in der ersten Version feststellen, dass der rekursive Aufruf von fact in den Multiplikationsausdruck eingespeist wird und daher der Zustand auf dem Stack gespeichert werden muss, wenn der rekursive Aufruf erfolgt. In der tail-rekursiven Version gibt es keinen anderen S-Ausdruck, der auf den Wert des rekursiven Aufrufs wartet, und da es keine weitere Arbeit zu tun gibt, muss der Zustand nicht auf dem Stack gespeichert werden. In der Regel verbrauchen tail-rekursive Funktionen von Scheme konstanten Stack-Speicherplatz.

Answer 3

Tail-Rekursion bedeutet, dass der rekursive Aufruf in der letzten logischen Anweisung des rekursiven Algorithmus zuletzt erfolgt.

Typischerweise haben Sie in der Rekursion eine Basisfall wodurch die rekursiven Aufrufe gestoppt werden und der Aufrufstapel geleert wird. Ein klassisches Beispiel, wenn auch eher in C als in Lisp, ist die Funktion factorial zur Veranschaulichung der Tail-Rekursion. Der rekursive Aufruf erfolgt nach die Überprüfung der Base-Case-Bedingung.

factorial(x, fac=1) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

Der erste Aufruf von factorial würde lauten factorial(n) donde fac=1 (Standardwert) und n ist die Zahl, für die die Fakultät berechnet werden soll.

Answer 4

Das bedeutet, dass Sie den Befehlszeiger nicht mehr auf den Stack legen müssen, sondern einfach an den Anfang einer rekursiven Funktion springen und die Ausführung fortsetzen können. So können Funktionen unbegrenzt rekursiv ausgeführt werden, ohne dass der Stack überläuft.

Ich schrieb eine blog mit grafischen Beispielen, die zeigen, wie die Stack Frames aussehen.

Answer 5

Der beste Weg für mich zu verstehen tail call recursion ist ein Spezialfall der Rekursion, bei dem die letzter Aufruf (oder der Tail Call) ist die Funktion selbst.

Vergleich der in Python bereitgestellten Beispiele:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^RECURSION

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^SCHWANZ-REKURSION

Wie Sie in der allgemeinen rekursiven Version sehen können, lautet der letzte Aufruf im Codeblock x + recsum(x - 1) . Nach dem Aufruf der recsum Methode gibt es einen weiteren Vorgang, der x + .. .

In der Tail-Rekursiv-Version ist der letzte Aufruf (oder der Tail-Aufruf) im Codeblock jedoch tailrecsum(x - 1, running_total + x) was bedeutet, dass der letzte Aufruf an die Methode selbst erfolgt und danach keine Operation mehr.

Dieser Punkt ist wichtig, weil die Tail-Rekursion, wie hier zu sehen, den Speicher nicht wachsen lässt, denn wenn die zugrunde liegende VM sieht, dass eine Funktion sich selbst an einer Tail-Position aufruft (der letzte Ausdruck, der in einer Funktion ausgewertet wird), beseitigt sie den aktuellen Stack-Frame, was als Tail Call Optimization (TCO) bekannt ist.

EDIT

NB. Bitte bedenken Sie, dass das obige Beispiel in Python geschrieben ist, dessen Laufzeitumgebung TCO nicht unterstützt. Dies ist nur ein Beispiel, um den Punkt zu erklären. TCO wird in Sprachen wie Scheme, Haskell usw. unterstützt.