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 ist ein Common Lisp-Beispiel, das mit Hilfe von Tail-Rekursion Faktorisierungen durchführt. Aufgrund der stapellosen Natur könnte man wahnsinnig große faktorielle Berechnungen durchführen ...

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

Und dann könnten Sie zum Spaß versuchen (format nil "~R" (! 25))

Answer 2

Eine Tail-Rekursion ist eine rekursive Funktion, bei der die Funktion sich selbst am Ende ("tail") der Funktion aufruft, in der nach der Rückkehr des rekursiven nach der Rückkehr des rekursiven Aufrufs durchgeführt wird. Viele Compiler optimieren, um einen rekursiven Aufruf in einen tail-rekursiven oder einen iterativen Aufruf zu verwandeln.

Betrachten Sie das Problem der Berechnung der Fakultät einer Zahl.

Ein direkter Ansatz wäre:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Angenommen, Sie rufen factorial(4) auf. Der Rekursionsbaum würde lauten:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

Die maximale Rekursionstiefe ist im obigen Fall O(n).

Betrachten Sie jedoch das folgende Beispiel:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

Der Rekursionsbaum für factTail(4) wäre:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

Auch hier ist die maximale Rekursionstiefe O(n), aber keiner der Aufrufe fügt eine zusätzliche Variable auf dem Stack hinzu. Daher kann der Compiler auf einen Stack verzichten.

Answer 3

Kurz gesagt, eine Tail-Rekursion hat den rekursiven Aufruf als zuletzt Anweisung in der Funktion, damit sie nicht auf den rekursiven Aufruf warten muss.

Es handelt sich also um eine Tail-Rekursion, d.h. N(x - 1, p * x) ist die letzte Anweisung in der Funktion, bei der der Compiler schlau genug ist, um herauszufinden, dass sie zu einer for-Schleife (Fakultät) optimiert werden kann. Der zweite Parameter p enthält den Wert des Zwischenprodukts.

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

Dies ist die nicht-rekursive Art, die obige faktorielle Funktion zu schreiben (obwohl einige C++-Compiler sie möglicherweise trotzdem optimieren können).

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

aber das ist es nicht:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

Ich habe einen langen Beitrag mit dem Titel " Verstehen der Tail-Rekursion - Visual Studio C++ - Baugruppenansicht "

Answer 4

Hier ist eine Perl 5 Version des tailrecsum Funktion, die bereits erwähnt wurde.

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

Answer 5

Dies ist ein Auszug aus Struktur und Interpretation von Computerprogrammen über Schwanzrekursion.

Bei der Gegenüberstellung von Iteration und Rekursion müssen wir darauf achten, dass wir den Begriff eines rekursiven Prozesses nicht mit dem Begriff eines rekursiven Prozedur. Wenn wir ein Verfahren als rekursiv bezeichnen, beziehen wir uns auf die syntaktische Tatsache, dass die Prozedurdefinition (entweder direkt oder indirekt) auf die Prozedur selbst verweist. Wenn wir aber einen Prozess als einem Muster folgend beschreiben, das z. B. linear rekursiv ist rekursiv ist, sprechen wir darüber, wie sich der Prozess entwickelt, nicht über die Syntax, wie eine Prozedur geschrieben ist. Es mag beunruhigend erscheinen, dass wir eine rekursive Prozedur wie fact-iter als Erzeugung eines iterativen Prozess bezeichnen. Der Prozess ist jedoch tatsächlich iterativ: Sein Zustand wird vollständig durch seine drei Zustandsvariablen erfasst, und ein Interpreter muss nur drei Variablen im Auge behalten, um den Prozess den Prozess auszuführen.

Ein Grund dafür, dass die Unterscheidung zwischen Prozess und Verfahren verwirrend sein kann, ist, dass die meisten Implementierungen gängiger Sprachen (einschließlich Ada, Pascal und C) so konzipiert sind, dass die Interpretation jeder rekursiven Prozedur Prozedur eine Menge an Speicher verbraucht, die mit der Anzahl der Prozeduraufrufe wächst, auch wenn der beschriebene Prozess im Prinzip, iterativ ist. Infolgedessen können diese Sprachen iterative iterative Prozesse nur durch den Rückgriff auf spezielle "Schleifenkonstrukte" wie do, repeat, until, for und while. Die Umsetzung von Scheme weist diesen Fehler nicht auf. Sie führt einen iterativen Prozess im konstanten Raum aus, selbst wenn der iterative Prozess durch eine rekursive Prozedur beschrieben wird. Eine Implementierung mit dieser Eigenschaft wird tail-recursive genannt. Mit einem tail-recursive Implementierung kann die Iteration durch den gewöhnlichen Prozeduraufrufmechanismus ausgedrückt werden, so dass spezielle Iterations Konstrukte nur als syntaktischer Zucker nützlich sind.