Obwohl man oft die folgenden als Beispiel faktorielles zu Tail-Call der Umwandlung:
int factorial(int n, int acc=1) {
if (n <= 1) return acc;
else return factorial(n-1, n*acc);
}
es ist nicht ganz richtig, da es Multiplikation erfordert sowohl assoziativ und kommutativ zu sein. (Multiplication ist assoziativ und kommutativ, aber die oben nicht für andere Operationen als Modell nicht dazu dienen, die diese Einschränkungen nicht erfüllen.) Eine bessere Lösung wäre:
int factorial(int n, int k=1, int acc=1) {
if (n == 0) return acc;
else return factorial(n-1, k+1, acc*k);
}
Dies auch als Modell dient, für die Fibonacci-Transformation:
int fibonacci(int n, int a=1, int b=0) {
if (n == 0) return a;
else return fibonacci(n-1, a+b, a);
}
beachten, dass diese die Sequenz berechnen am Anfang beginnen, wie zum Warteschlange anhängige Fortsetzungen in einer Aufrufliste entgegengesetzt. Sie sind strukturell eher der iterativen Lösung als der rekursiven Lösung. Im Gegensatz zum iterativen Programm ändern sie jedoch niemals eine Variable. Alle Bindungen sind konstant.Dies ist eine interessante und nützliche Eigenschaft; In diesen einfachen Fällen macht es keinen großen Unterschied, aber das Schreiben von Code ohne Neuzuweisung erleichtert einige Compiler-Optimierungen.
Wie auch immer, die letzte bietet ein Modell für Ihre rekursive Funktion; wie die Fibonacci-Sequenz, müssen wir die relevanten Vergangenheitswerte halten, aber wir müssen drei von ihnen statt zwei:
int mouse(int n, int a=1, int b=1, int c=1) {
if (n <=2) return a;
else return mouse(n-1, a*c+1, a, b);
}
Addenda
In Kommentaren wurden zwei Fragen aufgeworfen. Ich werde versuchen, sie (und einen weiteren) hier zu beantworten.
Zunächst sollte klar sein (aus einer Betrachtung der zugrunde liegenden Maschinenarchitektur, die kein Konzept des Funktionsaufrufs hat), dass jeder Funktionsaufruf als ein Goto umformuliert werden kann (möglicherweise mit nicht beschränktem Zwischenspeicher); Darüber hinaus kann jeder Goto als Tail-Call ausgedrückt werden. Es ist also möglich (aber nicht unbedingt schön), Rekursionen als Tail-Rekursion neu zu schreiben.
Der übliche Mechanismus ist "Continuation-Passing-Stil", die eine phantastische Art zu sagen, dass jedes Mal, wenn Sie eine Funktion aufrufen möchten, Sie stattdessen den Rest der aktuellen Funktion als eine neue Funktion (die "Fortsetzung") und übertrage diese Fortsetzung auf die aufgerufene Funktion. Da jede Funktion dann eine Fortsetzung als Argument erhält, muss sie jede Fortsetzung beenden, die sie mit einem Aufruf der Fortsetzung, die sie erhalten hat, erzeugt.
Das ist wahrscheinlich genug, um Ihren Kopf zu drehen, also werde ich es anders ausdrücken: Statt Argumente und eine Rückkehrposition auf den Stapel zu schieben und eine Funktion aufzurufen (die später zurückkehrt), drücken Sie Argumente und eine Fortsetzung Stelle auf den Stapel und gehe zu einer Funktion, die später zum Fortsetzungsort führt. Kurz gesagt, Sie machen den Stapel einfach zu einem expliziten Parameter, und dann müssen Sie nie mehr zurückkehren. Diese Art der Programmierung ist im ereignisgesteuerten Code üblich (siehe Python Twisted), und es ist ein echter Schmerz, zu schreiben (und zu lesen). Daher empfehle ich dringend, Compiler diese Transformation für Sie durchführen zu lassen, wenn Sie eine finden, die das tun wird.
@xxmouse vorgeschlagen, dass ich die Rekursion Gleichung aus einem Hut gezogen, und fragte, wie es abgeleitet wurde. Es ist einfach das Original Rekursion, sondern als Transformation eines einzelnen Tupel neu formuliert:
fn = fn-1*fn-3 + 1
=>
Fn = <Fn-11*Fn-13+1, Fn-11, Fn-12>
weiß ich nicht, ob das noch klarer, aber es ist das Beste, was ich tun kann. Sehen Sie sich das Beispiel mit den Fibonacci an, für einen etwas einfacheren Fall.
@j_random_hacker fragt, was die Grenzen dieser Transformation sind. Es funktioniert für eine rekursive Sequenz, in der jedes Element durch eine Formel der vorhergehenden k Elemente ausgedrückt werden kann, wobei k eine Konstante ist. Es gibt andere Möglichkeiten, eine Tail-Call-Rekursion zu erzeugen. Zum Beispiel:
// For didactic purposes only
bool is_odd(int n) { return n%2 == 1; }
int power(int x, int n, int acc=1) {
if (n == 0) return acc;
else if (is_odd(n)) return power(x, n-1, acc*x);
else return power(x*x, n/2, acc);
}
Obiges ist nicht das gleiche wie die übliche nicht-tail-Call-Rekursion, die ein anderes tut (aber gleichwertige und gleich lang) Folge von Multiplikationen.
int squared(n) { return n * n; }
int power(int x, int n) {
if (n == 0) return 1;
else if (is_odd(n)) return x * power(x, n-1));
else return squared(power(x, n/2));
}
Dank Alexey Frunse für den folgenden Test: Ausgang (ideone):
mouse(0) = 1
mouse(1) = 1
mouse(2) = 1
mouse(3) = 2
mouse(4) = 3
mouse(5) = 4
mouse(6) = 9
mouse(7) = 28
mouse(8) = 113
mouse(9) = 1018
wahre Endrekursion Sie erfordert entweder selbst den Stapel zu verarbeiten, schreiben Sie es in der Montage oder Compiler-Unterstützung haben. Ich glaube nicht, dass Perl es derzeit unterstützt. – Dai
Ich denke @Dai sind Sie mit Tail-Rekursion _removal_ verwirrt, die eine Compiler-Optimierung ist. Er fragt nur, ob ich zu einer tailrekursiven Funktion übergehen soll, denke ich. – Gene