Was ist Tail-Rekursion?

Question

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

Answer 1

Betrachten wir eine einfache Funktion, die die ersten N natürlichen Zahlen addiert. (z.B.. sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15 ).

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

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

Wenn Sie anrufen recsum(5) würde der JavaScript-Interpreter dies auswerten:

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 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

Beachten Sie, dass jeder rekursive Aufruf abgeschlossen sein muss, bevor der JavaScript-Interpreter die eigentliche Arbeit der Summenberechnung übernimmt.

Hier ist eine tail-rekursive Version der gleichen Funktion:

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

Hier die Abfolge der Ereignisse, die eintreten würden, wenn Sie tailrecsum(5) (das wäre in Wirklichkeit tailrecsum(5, 0) (wegen des standardmäßigen zweiten Arguments).

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

Im tail-rekursiven Fall wird bei jeder Auswertung des rekursiven Aufrufs die running_total aktualisiert wird.

_Hinweis: In der ursprünglichen Antwort wurden Beispiele aus Python verwendet. Diese wurden in JavaScript geändert, da Python-Interpreter keine Unterstützung für Optimierung des Heckaufrufs . Die Optimierung von Schwanzaufrufen ist jedoch Teil der ECMAScript 2015 Spezifikation die meisten JavaScript-Interpreter es nicht unterstützen ._

Answer 2

Unter traditionelle Rekursion Das typische Modell ist, dass Sie zuerst Ihre rekursiven Aufrufe durchführen und dann den Rückgabewert des rekursiven Aufrufs nehmen und das Ergebnis berechnen. Auf diese Weise erhalten Sie das Ergebnis Ihrer Berechnung erst, nachdem Sie von jedem rekursiven Aufruf zurückgekehrt sind.

Unter Schwanzrekursion 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 weitergeben. Dies führt dazu, dass die letzte Anweisung in Form von (return (recursive-function params)) . Grundsätzlich ist der Rückgabewert eines beliebigen rekursiven Schritts derselbe 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, den nächsten rekursiven Schritt auszuführen. Dies ermöglicht eine gewisse Optimierung. Mit einem entsprechend geschriebenen Compiler sollte es eigentlich nie zu einem Stapelüberlauf kommen kichern mit einem rekursiven Aufruf am Ende. Verwenden Sie einfach den aktuellen Stack-Frame für den nächsten Rekursionsschritt wieder. Ich bin mir ziemlich sicher, dass Lisp dies tut.

Answer 3

Ein wichtiger Punkt ist, dass die Tail-Rekursion im Wesentlichen mit einer Schleife gleichzusetzen ist. Das ist nicht nur eine Frage der Compiler-Optimierung, sondern eine grundlegende Tatsache der Ausdruckskraft. Dies gilt in beide Richtungen: Sie können jede Schleife der Form

while(E) { S }; return Q

donde E et Q sind Ausdrücke und S eine Folge von Anweisungen ist, und verwandeln Sie sie in eine rekursive Schwanzfunktion

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

Ja, natürlich, E , S y Q müssen definiert werden, um einen interessanten 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;
}

ist äquivalent zu der/den tail-recursiven 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 tail-rekursiven Funktion mit einer Funktion mit weniger Parametern ist eine gängige funktionale Redewendung).

Answer 4

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.

A Heckruf Die [Schwanzrekursion] ist eine Art "goto dressed als Aufruf. Ein Tail Call geschieht, wenn eine Funktion eine andere Funktion als letzte Aktion aufruft, so dass sie nichts anderes zu tun hat. Zum Beispiel im folgenden Code, der Aufruf an g ist ein Schwanzvergleich:

function f (x)
  return g(x)
end

Nach f ruft auf. g hat es nichts anderes zu tun. In solchen Situationen muss das Programm nicht zur aufrufenden Funktion zurückkehren Funktion zurückzukehren, wenn die aufgerufene Funktion endet. Daher wird nach dem Tail-Aufruf, muss das Programm keine Informationen Informationen über die aufrufende Funktion auf dem Stack zu speichern. ...

Da ein richtiger Schwanzaufruf keine Stapelplatz verwendet, gibt es keine Begrenzung für die Anzahl von "verschachtelten" Tail Calls, die ein Programm machen kann. Wir können zum Beispiel die folgende Funktion mit einer beliebigen Zahl als Argument aufrufen; sie wird niemals den Stapel überlaufen:

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

... Wie ich bereits sagte, ist ein Tail-Call eine Art von goto. Als solcher ist eine recht nützliche Anwendung von Tail-Aufrufen in Lua ist die Programmierung von Zustandsautomaten. Solche Anwendungen können jeden Zustand durch eine Funktion darstellen; um den Zustand ist der Wechsel zu (oder der Aufruf von) einer bestimmten Funktion. Lassen Sie uns als Beispiel ein einfaches Labyrinthspiel betrachten. Das Labyrinth hat mehrere Räume, jeder mit bis zu vier Türen: Norden, Süden, Osten und Westen. Bei jedem Schritt gibt der Benutzer eine Bewegungsrichtung ein. Befindet sich eine Tür in dieser Richtung gibt, geht der Benutzer in den den entsprechenden Raum; andernfalls wird das Programm eine Warnung aus. Das Ziel ist von einem Anfangsraum zu einem Endraum zu gehen Raum zu gelangen.

Dieses Spiel ist ein typischer Zustandsautomat, wobei der aktuelle Raum der Zustand ist. Wir können ein solches Labyrinth mit einer Funktion für jeden Raum implementieren. Wir verwenden Schwanz Aufrufe, um von einem Raum zum anderen zu anderen. Ein kleines Labyrinth mit vier Räumen könnte wie folgt 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 machen wie:

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

Es handelt sich dabei nicht um einen rekursiven Schwanz, da Sie nach dem rekursiven Aufruf in dieser Funktion noch etwas zu tun haben (1 hinzufügen). Wenn Sie eine sehr hohe Zahl eingeben, führt dies wahrscheinlich zu einem Stapelüberlauf.

Answer 5

Bei der regulären Rekursion schiebt jeder rekursive Aufruf einen weiteren Eintrag auf den Aufrufstapel. Wenn die Rekursion abgeschlossen ist, muss die Anwendung jeden Eintrag wieder ganz nach unten verschieben.

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

Grundsätzlich können Tail-Rekursionen zu Iterationen optimiert werden.