Was ist Schwanzrekursion?

Als ich anfing, Lisp zu lernen, bin ich auf den Begriff Schwanzrekursiv gestoßen . Was bedeutet es genau?

Stellen Sie sich eine einfache Funktion vor, die die ersten N natürlichen Zahlen addiert. (zB sum(5) = 1 + 2 + 3 + 4 + 5 = 15).

Hier ist eine einfache JavaScript-Implementierung, die Rekursion verwendet:

function recsum(x) {
    if (x === 1) {
        return x;
    } else {
        return x + recsum(x - 1);
    }
}

Wenn Sie anrufen recsum(5), bewertet der JavaScript-Interpreter Folgendes:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

Beachten Sie, wie jeder rekursive Aufruf abgeschlossen sein muss, bevor der JavaScript-Interpreter tatsächlich mit der Berechnung der Summe beginnt.

Hier ist eine rekursive Version derselben Funktion:

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

Hier ist die Abfolge von Ereignissen, die auftreten würden, wenn Sie aufrufen tailrecsum(5)würden (was tailrecsum(5, 0)aufgrund des zweiten Standardarguments effektiv wäre ).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

Im Schwanz-rekursiven Fall wird bei jeder Auswertung des rekursiven Aufrufs das running_totalaktualisiert.

Hinweis: In der ursprünglichen Antwort wurden Beispiele aus Python verwendet. Diese wurden in JavaScript geändert, da Python-Interpreter die Tail-Call-Optimierung nicht unterstützen . Während die Tail-Call-Optimierung Teil der ECMAScript 2015-Spezifikation ist , unterstützen sie die meisten JavaScript-Interpreter nicht .

Bei der herkömmlichen Rekursion besteht das typische Modell darin, dass Sie zuerst Ihre rekursiven Aufrufe ausführen und dann den Rückgabewert des rekursiven Aufrufs verwenden und das Ergebnis berechnen. Auf diese Weise erhalten Sie das Ergebnis Ihrer Berechnung erst, wenn Sie von jedem rekursiven Aufruf zurückgekehrt sind.

Bei der Endrekursion führen Sie zuerst Ihre Berechnungen durch und führen dann den rekursiven Aufruf aus, wobei Sie die Ergebnisse Ihres aktuellen Schritts an den nächsten rekursiven Schritt übergeben. Dies führt dazu, dass die letzte Aussage die Form von hat (return (recursive-function params)). Grundsätzlich ist der Rückgabewert eines bestimmten rekursiven Schritts der gleiche wie der Rückgabewert des nächsten rekursiven Aufrufs .

Dies hat zur Folge, dass Sie den aktuellen Stapelrahmen nicht mehr benötigen, sobald Sie bereit sind, Ihren nächsten rekursiven Schritt auszuführen. Dies ermöglicht eine gewisse Optimierung. Tatsächlich sollten Sie mit einem entsprechend geschriebenen Compiler niemals einen Stapelüberlauf- Snicker mit einem rekursiven Schwanzaufruf haben. Verwenden Sie einfach den aktuellen Stapelrahmen für den nächsten rekursiven Schritt. Ich bin mir ziemlich sicher, dass Lisp das tut.

Ein wichtiger Punkt ist, dass die Schwanzrekursion im Wesentlichen einer Schleife entspricht. Es geht nicht nur um die Optimierung des Compilers, sondern auch um die Ausdruckskraft. Dies geht in beide Richtungen: Sie können eine beliebige Schleife des Formulars nehmen

while(E) { S }; return Q

wo Eund Qsind Ausdrücke und Sist eine Folge von Anweisungen, und verwandeln Sie es in eine rekursive Schwanzfunktion

f() = if E then { S; return f() } else { return Q }

Natürlich E, Sund Qmüssen definiert werden einige interessante Wert über einige Variablen zu berechnen. Zum Beispiel die Schleifenfunktion

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

entspricht der (den) rekursiven Funktion (en)

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(Dieses "Umschließen" der Schwanzrekursionsfunktion mit einer Funktion mit weniger Parametern ist eine übliche Funktionssprache.)

Dieser Auszug aus dem Buch Programmieren in Lua zeigt, wie man eine richtige Schwanzrekursion macht (in Lua, sollte aber auch für Lisp gelten) und warum es besser ist.

Ein Tail Call [Tail Recursion] ist eine Art Goto, der als Call verkleidet ist. Ein Tail-Aufruf erfolgt, wenn eine Funktion als letzte Aktion eine andere aufruft, sodass sie nichts anderes zu tun hat. Im folgenden Code ist der Aufruf von gbeispielsweise ein Tail-Aufruf:

function f (x)
  return g(x)
end

Nach fAnrufen ghat es nichts mehr zu tun. In solchen Situationen muss das Programm nicht zur aufrufenden Funktion zurückkehren, wenn die aufgerufene Funktion endet. Daher muss das Programm nach dem Tail-Aufruf keine Informationen über die aufrufende Funktion im Stapel speichern. ...

Da ein ordnungsgemäßer Tail-Aufruf keinen Stapelspeicherplatz belegt, ist die Anzahl der "verschachtelten" Tail-Aufrufe, die ein Programm ausführen kann, unbegrenzt. Zum Beispiel können wir die folgende Funktion mit einer beliebigen Nummer als Argument aufrufen; es wird niemals über den Stapel laufen:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

... Wie ich bereits sagte, ist ein Tail Call eine Art Goto. Daher ist die Programmierung von Zustandsmaschinen eine recht nützliche Anwendung für ordnungsgemäße Tail-Aufrufe in Lua. Solche Anwendungen können jeden Zustand durch eine Funktion darstellen; Um den Status zu ändern, muss eine bestimmte Funktion aufgerufen (oder aufgerufen) werden. Betrachten wir als Beispiel ein einfaches Labyrinthspiel. Das Labyrinth hat mehrere Räume mit jeweils bis zu vier Türen: Nord, Süd, Ost und West. Bei jedem Schritt gibt der Benutzer eine Bewegungsrichtung ein. Befindet sich in dieser Richtung eine Tür, geht der Benutzer in den entsprechenden Raum. Andernfalls gibt das Programm eine Warnung aus. Das Ziel ist es, von einem Anfangsraum zu einem Endraum zu gelangen.

Dieses Spiel ist eine typische Zustandsmaschine, bei der der aktuelle Raum der Zustand ist. Wir können ein solches Labyrinth mit einer Funktion für jeden Raum implementieren. Wir verwenden Tail Calls, um von einem Raum in einen anderen zu wechseln. Ein kleines Labyrinth mit vier Räumen könnte so aussehen:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

Sie sehen also, wenn Sie einen rekursiven Aufruf tätigen wie:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

Dies ist nicht rekursiv, da Sie in dieser Funktion nach dem rekursiven Aufruf noch etwas zu tun haben (1 hinzufügen). Wenn Sie eine sehr hohe Zahl eingeben, führt dies wahrscheinlich zu einem Stapelüberlauf.

Bei Verwendung der regulären Rekursion schiebt jeder rekursive Aufruf einen anderen Eintrag auf den Aufrufstapel. Wenn die Rekursion abgeschlossen ist, muss die App jeden Eintrag ganz nach unten entfernen.

Bei der Endrekursion kann der Compiler je nach Sprache den Stapel möglicherweise auf einen Eintrag reduzieren, sodass Sie Speicherplatz sparen ... Eine große rekursive Abfrage kann tatsächlich einen Stapelüberlauf verursachen.

Grundsätzlich können Schwanzrekursionen in Iterationen optimiert werden.

Die Jargon-Datei enthält Folgendes zur Definition der Schwanzrekursion:

Schwanzrekursion /n./

Wenn Sie es noch nicht satt haben, sehen Sie sich die Schwanzrekursion an.

Anstatt es mit Worten zu erklären, hier ein Beispiel. Dies ist eine Schemaversion der Fakultätsfunktion:

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

Hier ist eine Version von Fakultät, die schwanzrekursiv 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 Status beim Ausführen des rekursiven Aufrufs auf dem Stapel gespeichert werden muss. In der rekursiven Version wartet kein anderer S-Ausdruck auf den Wert des rekursiven Aufrufs, und da keine weitere Arbeit zu erledigen ist, muss der Status nicht auf dem Stapel gespeichert werden. In der Regel verwenden schema-rekursive Funktionen einen konstanten Stapelraum.

Die Schwanzrekursion bezieht sich darauf, dass der rekursive Aufruf im letzten Logikbefehl im rekursiven Algorithmus der letzte ist.

In der Regel haben Sie bei der Rekursion einen Basisfall, der die rekursiven Aufrufe stoppt und den Aufrufstapel öffnet. Um ein klassisches Beispiel zu verwenden, obwohl mehr C-ish als Lisp, veranschaulicht die Fakultätsfunktion die Schwanzrekursion. Der rekursive Aufruf erfolgt nach Überprüfung der Basisfallbedingung.

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

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

Dies bedeutet, dass Sie nicht den Befehlszeiger auf dem Stapel drücken müssen, sondern einfach an den Anfang einer rekursiven Funktion springen und die Ausführung fortsetzen können. Dadurch können Funktionen unbegrenzt wiederholt werden, ohne dass der Stapel überläuft.

Ich habe einen Blog- Beitrag zu diesem Thema geschrieben, der grafische Beispiele dafür enthält, wie die Stapelrahmen aussehen.

Hier ist ein kurzer Code-Ausschnitt, der zwei Funktionen vergleicht. Die erste ist die traditionelle Rekursion zum Ermitteln der Fakultät einer bestimmten Zahl. Die zweite verwendet die Schwanzrekursion.

Sehr einfach und intuitiv zu verstehen.

Eine einfache Methode, um festzustellen, ob eine rekursive Funktion eine rekursive Endfunktion ist, besteht darin, dass sie im Basisfall einen konkreten Wert zurückgibt. Das bedeutet, dass es nicht 1 oder true oder ähnliches zurückgibt. Es wird höchstwahrscheinlich eine Variante eines der Methodenparameter zurückgeben.

Eine andere Möglichkeit besteht darin, festzustellen, ob der rekursive Aufruf frei von Additionen, Arithmetik, Änderungen usw. ist. Dies bedeutet, dass es sich nur um einen reinen rekursiven Aufruf handelt.

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);
    }
}

Der beste Weg für mich zu verstehen tail call recursionist ein Sonderfall der Rekursion, wo der letzte Anruf (oder der Endaufruf) die Funktion selbst ist.

Vergleich der in Python bereitgestellten Beispiele:

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

^ Rekursion

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

^ SCHWANZREKURSION

Wie Sie in der allgemeinen rekursiven Version sehen können, ist der letzte Aufruf im Codeblock x + recsum(x - 1). Nach dem Aufruf der recsumMethode gibt es also eine andere Operation:x + .. :

In der rekursiven Endversion ist jedoch der letzte Aufruf (oder der Endaufruf) im Codeblock tailrecsum(x - 1, running_total + x) der letzte Aufruf der Methode selbst und keine Operation danach.

Dieser Punkt ist wichtig, da die Tail-Rekursion, wie hier gezeigt, den Speicher nicht wachsen lässt, da der aktuelle Stapelrahmen eliminiert wird, wenn die zugrunde liegende VM sieht, dass sich eine Funktion an einer Tail-Position aufruft (der letzte Ausdruck, der in einer Funktion ausgewertet wird) wird als Tail Call Optimization (TCO) bezeichnet.

BEARBEITEN

NB. Beachten Sie, dass das obige Beispiel in Python geschrieben ist, dessen Laufzeit 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

In Java ist hier eine mögliche rekursive Implementierung der Fibonacci-Funktion:

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);
}

Vergleichen Sie dies mit der rekursiven Standardimplementierung:

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

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

Grundsätzlich ist es ein Programmierstil, bei dem der rekursive Aufruf das letzte ist, was Sie tun.

Hier ist ein Common Lisp-Beispiel, das Fakultäten mithilfe der Schwanzrekursion ausfü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 es zum Spaß versuchen (format nil "~R" (! 25))

Kurz gesagt, eine Schwanzrekursion hat den rekursiven Aufruf als letzte Anweisung in der Funktion, damit sie nicht auf den rekursiven Aufruf warten muss.

Dies ist also eine Schwanzrekursion, dh N (x - 1, p * x) ist die letzte Anweisung in der Funktion, bei der der Compiler klug ist, herauszufinden, dass sie für eine for-Schleife (Fakultät) optimiert werden kann. Der zweite Parameter p trägt den Zwischenproduktwert.

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

Dies ist die nicht schwanzrekursive Art, die obige Fakultätsfunktion 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 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 " Grundlegendes zur Schwanzrekursion - Visual Studio C ++ - Assembly View " geschrieben.

Hier ist eine Perl 5-Version der tailrecsumzuvor erwähnten Funktion.

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
}

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

Im Gegensatz zu Iteration und Rekursion müssen wir darauf achten, den Begriff eines rekursiven Prozesses nicht mit dem Begriff eines rekursiven Verfahrens zu verwechseln. Wenn wir eine Prozedur als rekursiv beschreiben, beziehen wir uns auf die syntaktische Tatsache, dass sich die Prozedurdefinition (entweder direkt oder indirekt) auf die Prozedur selbst bezieht. Wenn wir einen Prozess jedoch so beschreiben, dass er einem Muster folgt, das beispielsweise linear rekursiv ist, sprechen wir darüber, wie sich der Prozess entwickelt, und nicht über die Syntax, wie eine Prozedur geschrieben wird. Es mag beunruhigend erscheinen, dass wir eine rekursive Prozedur wie fact-iter als Erzeugung eines iterativen Prozesses bezeichnen. Der Prozess ist jedoch wirklich iterativ: Sein Status wird vollständig von seinen drei Statusvariablen erfasst, und ein Interpreter muss nur drei Variablen verfolgen, um den Prozess auszuführen.

Ein Grund dafür, dass die Unterscheidung zwischen Prozess und Prozedur verwirrend sein kann, besteht darin, dass die meisten Implementierungen gängiger Sprachen (einschließlich Ada, Pascal und C) so gestaltet sind, dass die Interpretation einer rekursiven Prozedur eine Menge an Speicher verbraucht, die mit der wächst Anzahl der Prozeduraufrufe, auch wenn der beschriebene Prozess im Prinzip iterativ ist. Infolgedessen können diese Sprachen iterative Prozesse nur beschreiben, indem sie auf spezielle „Schleifenkonstrukte“ zurückgreifen, wie z. B. do, repeat, till, for und while. Die Umsetzung des Programms teilt diesen Mangel nicht. Es wird ein iterativer Prozess in konstantem Raum ausgeführt, selbst wenn der iterative Prozess durch eine rekursive Prozedur beschrieben wird. Eine Implementierung mit dieser Eigenschaft wird als tail-rekursiv bezeichnet. Bei einer schwanzrekursiven Implementierung kann die Iteration unter Verwendung des gewöhnlichen Prozeduraufrufmechanismus ausgedrückt werden, so dass spezielle Iterationskonstrukte nur als syntaktischer Zucker nützlich sind.

Die rekursive Funktion ist eine Funktion, die von selbst aufruft

Es ermöglicht Programmierern, effiziente Programme mit einer minimalen Menge an Code zu schreiben .

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

Ich werde sowohl die einfache rekursive Funktion als auch die Schwanzrekursive Funktion erklären

Um eine einfache rekursive Funktion zu schreiben

1. Der erste zu berücksichtigende Punkt ist, wann Sie sich entscheiden sollten, aus der Schleife herauszukommen, die die if-Schleife ist
2. Der zweite 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 werden soll

else 
     return n * fact(n-1);

Ist die eigentliche Verarbeitung durchzuführen

Lassen Sie mich die Aufgabe einzeln aufteilen, um das Verständnis zu erleichtern.

Lassen Sie uns sehen, was intern passiert, wenn ich renne fact(4)

1. Einsetzen von n = 4

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

IfDie Schleife schlägt fehl und geht zur elseSchleife, sodass sie zurückkehrt4 * fact(3)

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

   Einsetzen von n = 3

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

IfDie Schleife schlägt fehl und geht zur elseSchleife

so kehrt es zurück 3 * fact(2)

Denken Sie daran, wir haben `` `4 * fact (3)` `genannt

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

Soweit hat der Stack 4 * fact(3) = 4 * 3 * fact(2)

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

   Einsetzen von n = 2

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

IfDie Schleife schlägt fehl und geht zur elseSchleife

so kehrt es zurück 2 * fact(1)

Denken Sie daran, wir haben angerufen 4 * 3 * fact(2)

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

Soweit hat der Stack 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

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

   Einsetzen von n = 1

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

If Schleife ist wahr

so kehrt es zurück 1

Denken Sie daran, wir haben angerufen 4 * 3 * 2 * fact(1)

Die Ausgabe für fact(1) = 1

Soweit hat der Stack 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Schließlich ist das Ergebnis von Tatsache (4) = 4 · 3 · 2 · 1 = 24

Die 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. Einsetzen 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);
    }
}

IfDie Schleife schlägt fehl und geht zur elseSchleife, sodass sie zurückkehrtfact(3, 4)

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

   Einsetzen von n = 3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

IfDie Schleife schlägt fehl und geht zur elseSchleife

so kehrt es zurück fact(2, 12)

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

   Einsetzen von n = 2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

IfDie Schleife schlägt fehl und geht zur elseSchleife

so kehrt es zurück fact(1, 24)

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

   Einsetzen von 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

so kehrt es zurück running_total

Die Ausgabe für running_total = 24

Schließlich ist das Ergebnis der Tatsache (4,1) = 24

Schwanzrekursion ist das Leben, das Sie gerade leben. Sie recyceln ständig denselben Stapelrahmen immer wieder, da es keinen Grund oder keine Möglichkeit gibt, zu einem "vorherigen" Rahmen zurückzukehren. Die Vergangenheit ist vorbei und erledigt, so dass sie verworfen werden kann. Sie erhalten einen Frame, der sich für immer in die Zukunft bewegt, bis Ihr Prozess unweigerlich zum Erliegen kommt.

_{Die Analogie bricht zusammen, wenn Sie bedenken, dass einige Prozesse möglicherweise zusätzliche Frames verwenden, aber dennoch als schwanzrekursiv betrachtet werden, wenn der Stapel nicht unendlich wächst.}

Eine Schwanzrekursion ist eine rekursive Funktion, bei der sich die Funktion am Ende ("Schwanz") der Funktion aufruft, bei der nach der Rückkehr des rekursiven Aufrufs keine Berechnung durchgeführt wird. Viele Compiler optimieren, um einen rekursiven Aufruf in einen rekursiven oder einen iterativen Endaufruf zu ändern.

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

Ein einfacher Ansatz wäre:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Angenommen, Sie nennen Fakultät (4). Der Rekursionsbaum wäre:

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

Die maximale Rekursionstiefe im obigen Fall beträgt 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);

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 beträgt die maximale Rekursionstiefe O (n), aber keiner der Aufrufe fügt dem Stapel eine zusätzliche Variable hinzu. Daher kann der Compiler auf einen Stapel verzichten.

Die Schwanzrekursion ist im Vergleich zur normalen Rekursion ziemlich schnell. Dies ist schnell, da die Ausgabe des Ahnenaufrufs nicht im Stapel geschrieben wird, um den Überblick zu behalten. Bei normaler Rekursion rufen alle Vorfahren die im Stapel geschriebene Ausgabe auf, um den Überblick zu behalten.

Eine Schwanzrekursionsfunktion ist eine rekursive Funktion, bei der die letzte Operation, die sie vor der Rückkehr ausführt, der rekursive Funktionsaufruf ist. Das heißt, der Rückgabewert des rekursiven Funktionsaufrufs wird sofort zurückgegeben. Zum Beispiel würde Ihr Code folgendermaßen aussehen:

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

Compiler und Interpreter, die die Tail-Call-Optimierung oder die Tail-Call-Eliminierung implementieren , können 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), bietet das Schreiben Ihres Codes auf diese Weise keinen zusätzlichen Vorteil.

Dies ist beispielsweise eine standardmäßige rekursive Fakultätsfunktion 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)

Und dies ist eine rekursive Tail-Call-Version der Fakultätsfunktion:

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 dies Python-Code ist, keine Tail-Call-Optimierung durchführt. Wenn Sie Ihren Code so anordnen, hat dies keinen Laufzeitvorteil.)

Möglicherweise müssen Sie Ihren Code etwas unleserlicher machen, um die Tail-Call-Optimierung nutzen zu können, wie im faktoriellen Beispiel gezeigt. (Zum Beispiel ist der Basisfall jetzt etwas unintuitiv und der accumulatorParameter wird effektiv als eine Art globale Variable verwendet.)

Der Vorteil der Tail-Call-Optimierung besteht jedoch darin, dass Stapelüberlauffehler vermieden werden. (Ich werde bemerken, dass Sie denselben Vorteil erzielen können, indem Sie einen iterativen Algorithmus anstelle eines rekursiven verwenden.)

Stapelüberläufe werden verursacht, wenn auf den Aufrufstapel zu viele Frame-Objekte verschoben wurden. Ein Frame-Objekt wird beim Aufruf einer Funktion auf den Aufrufstapel verschoben und beim Zurückkehren der Funktion vom Aufrufstapel entfernt. Rahmenobjekte enthalten Informationen wie lokale Variablen und welche Codezeile bei der Rückkehr der Funktion zurückgegeben werden soll.

Wenn Ihre rekursive Funktion zu viele rekursive Aufrufe ohne Rückgabe ausführt, kann der Aufrufstapel sein Rahmenobjektlimit überschreiten. (Die Anzahl variiert je nach Plattform. In Python sind es standardmäßig 1000 Frame-Objekte.) Dies führt zu einem Stapelüberlauffehler . (Hey, daher kommt der Name dieser Website!)

Wenn Ihre rekursive Funktion jedoch als letztes den rekursiven Aufruf ausführt und seinen Rückgabewert zurückgibt, gibt es keinen Grund, das aktuelle Frame-Objekt auf dem Aufrufstapel zu belassen. Wenn nach dem rekursiven Funktionsaufruf kein Code vorhanden ist, gibt es keinen Grund, an den lokalen Variablen des aktuellen Frame-Objekts festzuhalten. So können wir das aktuelle Frame-Objekt sofort entfernen, anstatt es auf dem Aufrufstapel zu belassen. Das Endergebnis davon ist, dass Ihr Aufrufstapel nicht größer wird und daher keinen Stapelüberlauf verursachen kann.

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 haben Sie möglicherweise den Code in Ihrer rekursiven Funktion neu angeordnet, um die Tail-Call-Optimierung zu nutzen, und es liegt an Ihnen, ob diese potenzielle Verringerung der Lesbarkeit die Optimierung wert ist.

Um einige der Hauptunterschiede zwischen Tail-Call-Rekursion und Nicht-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 der Schwanzrekursion in C #, F # und C ++ \ CLI .

C # optimiert nicht für die Tail-Call-Rekursion, während F # dies tut.

Die prinzipiellen Unterschiede betreffen Schleifen gegenüber der Lambda-Rechnung. C # wurde unter Berücksichtigung von Schleifen entworfen, während F # aus den Prinzipien der Lambda-Rechnung aufgebaut ist. Ein sehr gutes (und kostenloses) Buch über die Prinzipien der Lambda-Rechnung finden Sie unter Struktur und Interpretation von Computerprogrammen von Abelson, Sussman und Sussman .

In Bezug auf Tail Calls in F # finden Sie einen sehr guten Einführungsartikel unter Detaillierte Einführung in Tail Calls in F # . Schließlich ist hier ein Artikel, der den Unterschied zwischen Nicht-Schwanz-Rekursion und Schwanz-Anruf-Rekursion (in F #) behandelt: Schwanz-Rekursion vs. Nicht-Schwanz-Rekursion in Fis .

Wenn Sie mehr über die Designunterschiede der Tail-Call-Rekursion zwischen C # und F # erfahren möchten, lesen Sie Generieren des Tail-Call-Opcodes in C # und F # .

Wenn Sie wissen möchten, unter welchen Bedingungen der C # -Compiler Tail-Call-Optimierungen durchführen kann, lesen Sie diesen Artikel: JIT CLR-Tail-Call-Bedingungen .

Es gibt zwei grundlegende Arten von Rekursionen: Kopfrekursion und Schwanzrekursion.

Bei der Kopfrekursion führt eine Funktion ihren rekursiven Aufruf durch und führt dann weitere Berechnungen durch, beispielsweise unter Verwendung des Ergebnisses des rekursiven Aufrufs.

In einer rekursiven Endfunktion werden alle Berechnungen zuerst ausgeführt, und der rekursive Aufruf ist das Letzte, was geschieht.

Entnommen aus diesem super tollen Beitrag. Bitte lesen Sie es.

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

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

Schwanzrekursion bedeutet die Rekursion, die die Funktion abschließt:

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

Sehen Sie, das Letzte, was eine unendliche Funktion (Prozedur im Schema-Jargon) tut, ist, sich selbst aufzurufen. Ein weiteres (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 Helper-Prozedur ist das LETZTE, was es tut, wenn die Linke nicht Null ist, sich selbst aufzurufen (NACH Nachteile von etwas und cdr etwas). So ordnen Sie im Grunde eine Liste zu.

Die Schwanzrekursion hat den großen Vorteil, dass der Interpreter (oder Compiler, abhängig von Sprache und Hersteller) sie optimieren und in etwas umwandeln kann, das einer while-Schleife entspricht. Tatsächlich wird in der Schematradition die meiste "for" - und "while" -Schleife in einer Schwanzrekursionsmethode durchgeführt (meines Wissens gibt es keine for and while).

Diese Frage hat viele gute Antworten ... aber ich kann nicht anders, als mich mit einer alternativen Sichtweise zu beschäftigen, wie man "Schwanzrekursion" oder zumindest "richtige Schwanzrekursion" definiert. Nämlich: sollte man es als eine Eigenschaft eines bestimmten Ausdrucks in einem Programm betrachten? Oder sollte man es als eine Eigenschaft einer Implementierung einer Programmiersprache betrachten ?

Für mehr über die letztere Ansicht gibt es ein klassisches Papier von Will Clinger, "Proper Tail Recursion and Space Efficiency" (PLDI 1998), das "Proper Tail Recursion" als eine Eigenschaft einer Programmiersprachenimplementierung definiert. Die Definition ist so aufgebaut, dass Implementierungsdetails ignoriert werden können (z. B. ob der Aufrufstapel tatsächlich über den Laufzeitstapel oder über eine vom Heap zugewiesene verknüpfte Liste von Frames dargestellt wird).

Um dies zu erreichen, wird eine asymptotische Analyse verwendet: nicht die Programmausführungszeit, wie man normalerweise sieht, sondern die Nutzung des Programmraums . Auf diese Weise ist die Speicherplatznutzung einer Heap-zugewiesenen verknüpften Liste im Vergleich zu einem Laufzeitaufrufstapel asymptotisch äquivalent. Man kann also dieses Implementierungsdetail der Programmiersprache ignorieren (ein Detail, das in der Praxis sicherlich ziemlich wichtig ist, aber das Wasser ziemlich trüben kann, wenn man versucht festzustellen, ob eine bestimmte Implementierung die Anforderung erfüllt, "rekursiv für Eigenschaftsschwänze" zu sein). )

Das Papier ist aus mehreren Gründen eine sorgfältige Untersuchung wert:

• Es gibt eine induktive Definition der Tail-Ausdrücke und Tail-Aufrufe eines Programms. (Eine solche Definition und warum solche Anrufe wichtig sind, scheint Gegenstand der meisten anderen hier gegebenen Antworten zu sein.)

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

  Definition 1 Die Endausdrücke eines im Kernschema geschriebenen Programms werden induktiv wie folgt definiert.

  1. Der Körper eines Lambda-Ausdrucks ist ein Schwanzausdruck
  2. Wenn (if E0 E1 E2)es sich um einen Schwanzausdruck handelt, sind beide E1und E2Schwanzausdrücke.
  3. Nichts anderes ist ein Schwanzausdruck.

  Definition 2 Ein Tail-Aufruf ist ein Tail-Ausdruck, der ein Prozeduraufruf ist.

(Ein rekursiver Tail-Aufruf oder, wie in der Veröffentlichung angegeben, "Self-Tail-Aufruf" ist ein Sonderfall eines Tail-Aufrufs, bei dem die Prozedur selbst aufgerufen wird.)

• Es enthält formale Definitionen für sechs verschiedene "Maschinen" zur Bewertung des Kernschemas, wobei jede Maschine das gleiche beobachtbare Verhalten aufweist, mit Ausnahme der asymptotischen Raumkomplexitätsklasse, in der sich jede befindet.

  Nachdem Sie beispielsweise Definitionen für Computer mit jeweils 1. stapelbasierter Speicherverwaltung, 2. Speicherbereinigung, aber keinen Endaufrufen, 3. Speicherbereinigung und Endaufrufen angegeben haben, wird das Papier mit noch fortschrittlicheren Speicherverwaltungsstrategien fortgesetzt, z 4. "evlis tail recursion", bei der die Umgebung bei der Auswertung des letzten Unterausdrucksarguments in einem tail call nicht erhalten bleiben muss, 5. Reduzieren der Umgebung eines Abschlusses auf nur die freien Variablen dieses Abschlusses und 6. sogenannte "Safe-for-Space" -Semantik, wie sie von Appel und Shao definiert wurde .

• Um zu beweisen, dass die Maschinen tatsächlich zu sechs verschiedenen Klassen der Raumkomplexität gehören, enthält das Papier für jedes verglichene Maschinenpaar konkrete Beispiele für Programme, die eine asymptotische Raumvergrößerung auf einer Maschine, jedoch nicht auf der anderen, aufdecken.

(Wenn ich jetzt meine Antwort durchlese, bin ich mir nicht sicher, ob es mir tatsächlich gelungen ist, die entscheidenden Punkte des Clinger-Papiers zu erfassen . Leider kann ich momentan nicht mehr Zeit für die Entwicklung dieser Antwort verwenden.)

Viele Leute haben hier bereits die Rekursion erklärt. Ich möchte einige Gedanken zu einigen Vorteilen anführen, die die Rekursion aus dem Buch „Parallelität in .NET, moderne Muster der gleichzeitigen und parallelen Programmierung“ von Riccardo Terrell bietet:

„Funktionale Rekursion ist der natürliche Weg, um in FP zu iterieren, da sie eine Mutation des Zustands vermeidet. Während jeder Iteration wird stattdessen ein neuer Wert an den Schleifenkonstruktor übergeben, um aktualisiert (mutiert) zu werden. Darüber hinaus kann eine rekursive Funktion erstellt werden, die Ihr Programm modularer macht und Möglichkeiten zur Nutzung der Parallelisierung bietet. "

Hier sind auch einige interessante Anmerkungen aus demselben Buch über die Schwanzrekursion:

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

HINWEIS Der Hauptgrund für einen Tail-Aufruf als Optimierung ist die Verbesserung der Datenlokalität, der Speichernutzung und der Cache-Nutzung. Bei einem Tail-Call verwendet der Angerufene denselben Stapelplatz wie der Caller. Dies reduziert den Speicherdruck. Der Cache wird geringfügig verbessert, da derselbe Speicher für nachfolgende Anrufer wiederverwendet wird und im Cache verbleiben kann, anstatt eine ältere Cache-Zeile zu entfernen, um Platz für eine neue Cache-Zeile zu schaffen.