Frage Was ist eine Schwanzrekursion?

Im traditionelle RekursionDas typische Modell besteht darin, dass Sie zuerst Ihre rekursiven Aufrufe durchfü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.

Im Schwanzrekursion, führen Sie zuerst Ihre Berechnungen aus und führen Sie 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 in Form von (return (recursive-function params)). Grundsätzlich ist der Rückgabewert eines gegebenen rekursiven Schrittes derselbe wie der Rückgabewert des nächsten rekursiven Aufrufs.

Die Konsequenz daraus ist, dass Sie, sobald Sie bereit sind, Ihren nächsten rekursiven Schritt auszuführen, den aktuellen Stapelrahmen nicht mehr benötigen. Dies ermöglicht eine gewisse Optimierung. Mit einem entsprechend geschriebenen Compiler sollten Sie niemals einen Stack-Überlauf haben kichern mit einem rekursiven Tail-Aufruf. Verwenden Sie einfach den aktuellen Stapelrahmen für den nächsten rekursiven Schritt. Ich bin mir ziemlich sicher, dass Lisp das macht.

Ein wichtiger Punkt ist, dass die Tail-Rekursion im Wesentlichen der Schleifenbildung entspricht. Es geht nicht nur um Compiler-Optimierung, sondern um eine grundlegende Aussagekraft. Das geht in beide Richtungen: Sie können jede Schleife des Formulars nehmen

while(E) { S }; return Q

woher E und Q sind Ausdrücke und S ist eine Abfolge von Anweisungen und wandelt sie in eine tail rekursive Funktion um

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

Na sicher, E, S, und Q müssen definiert werden, um einige interessante Werte ü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 tail-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 "Wrapping" der tailrekursiven Funktion mit einer Funktion mit weniger Parametern ist ein übliches Funktionsidiom.)

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

EIN Schwanzanruf [Tail Rekursion] ist eine Art von gekleidet   als Anruf. Ein Tail Call findet statt, wenn a   Funktion ruft eine andere als ihre letzte auf   Aktion, so hat es nichts anderes zu tun.   Zum Beispiel im folgenden Code,   der Anruf zu g ist ein Tail-Call:

function f (x)
  return g(x)
end

Nach f Anrufe gEs hat nichts anderes   machen. In solchen Situationen das Programm   muss nicht zum Anrufer zurückkehren   Funktion wenn die aufgerufene Funktion   endet. Daher, nach dem Rückruf,   Das Programm muss keine behalten   Informationen über die aufrufende Funktion   im Stapel. ...

Weil ein richtiger Tail Call nein verwendet   Stapelplatz, es gibt keine Grenze für die   Anzahl der "verschachtelten" Tail-Aufrufe, die a   Programm kann machen. Zum Beispiel können wir   Rufen Sie die folgende Funktion mit an   Zahl als Argument; es wird nie   Überlauf den Stapel:

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

... Wie ich bereits sagte, ist ein Tail Call ein   irgendwie goto. Als solches, ziemlich nützlich   Anwendung von richtigen Schwanz ruft herein   Lua dient zum Programmieren von Zustandsautomaten.   Solche Anwendungen können jeweils repräsentieren   Zustand durch eine Funktion; den Staat wechseln   ist, zu einem bestimmten zu gehen (oder zu nennen)   Funktion. Als ein Beispiel, lassen Sie uns   Betrachten Sie ein einfaches Labyrinth-Spiel. Das Labyrinth   hat mehrere Zimmer mit jeweils bis zu   vier Türen: Norden, Süden, Osten und   Westen. Bei jedem Schritt gibt der Benutzer ein ein   Bewegungsrichtung. Wenn da eine Tür ist   In dieser Richtung geht der Benutzer zu   der entsprechende Raum; ansonsten der   Programm druckt eine Warnung. Das Ziel ist   von einem anfänglichen Raum zu einem Finale zu gehen   Zimmer.

Dieses Spiel ist eine typische Staatsmaschine,   wo der aktuelle Raum der Staat ist.   Wir können ein solches Labyrinth mit einem implementieren   Funktion für jeden Raum. Wir benutzen Schwanz   Anrufe von einem Raum zu bewegen   Ein weiterer. 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 wie:

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

Dies ist nicht tail-rekursiv, da Sie nach dem rekursiven Aufruf immer noch Aufgaben in dieser Funktion ausführen müssen (1). Wenn Sie eine sehr hohe Zahl eingeben, wird wahrscheinlich ein Stapelüberlauf verursacht.

Bei Verwendung der regulären Rekursion drückt jeder rekursive Aufruf einen weiteren Eintrag auf den Aufrufstapel. Wenn die Rekursion abgeschlossen ist, muss die App jeden Eintrag wieder ganz zurückgeben.

Bei der Tail-Rekursion kann der Compiler den Stack auf einen Eintrag reduzieren, so dass Sie Speicherplatz sparen. Eine große rekursive Abfrage kann tatsächlich einen Stack-Überlauf verursachen.

Grundsätzlich können Tail-Rekursionen in Iteration optimiert werden.

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

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

Hier ist eine faktorielle Version, 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 zur Tatsache in den Multiplikationsausdruck eingegeben wird, und daher muss der Zustand auf dem Stapel gespeichert werden, wenn der rekursive Aufruf ausgeführt wird. In der tailrekursiven Version wartet kein anderer S-Ausdruck auf den Wert des rekursiven Aufrufs, und da keine weitere Arbeit zu erledigen ist, muss der Zustand nicht auf dem Stapel gespeichert werden. In der Regel verwenden rekursive Funktionen des Schemas stack stack space.

Die Jargon-Datei sagt Folgendes über die Definition der Tail-Rekursion:

Schwanzrekursion /n./

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

Die Tail-Rekursion bezieht sich auf den rekursiven Aufruf, der in der letzten logischen Anweisung im rekursiven Algorithmus zuletzt ist.

Typischerweise haben Sie in der Rekursion ein Basis-Fall Das stoppt die rekursiven Aufrufe und beginnt mit dem Aufruf des Aufruf-Stacks. Um ein klassisches Beispiel zu verwenden, obwohl es mehr C-ish als Lisp ist, veranschaulicht die Fakultätefunktion die Tail-Rekursion. Der rekursive Aufruf erfolgt nach Überprüfung des Grundzustands

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

Beachten Sie, dass der anfängliche Aufruf von factorial factorial (n, 1) sein muss, wobei n die Nummer ist, für die das factorial berechnet werden soll.

Es bedeutet, dass Sie den Anweisungszeiger nicht einfach auf den Stack schieben müssen, sondern einfach an den Anfang einer rekursiven Funktion springen und die Ausführung fortsetzen können. Dadurch können Funktionen unbegrenzt recursen, ohne den Stack zu überlasten.

Ich schrieb ein Blog Post zu dem Thema, das grafische Beispiele dafür hat, wie die Stack-Frames aussehen.