Ich verstehe die Schwanzrekursion falsch. nach zu dieser stackoverflow-Frage R unterstützt keine Tail-Rekursion. Betrachten wir jedoch die folgenden Funktionen, um die n-te Fibonacci-Zahl zu berechnen:
Iterative Version:
%Vor%"Naive" rekursive Version:
%Vor%Und schließlich ein Beispiel, das ich fand, dass Tail Call rekursiv sein sollte:
%Vor%Wenn wir uns nun die Spuren ansehen, wenn diese Funktionen aufgerufen werden, erhalten wir folgendes:
%Vor% In den Fällen Fibo(25) und FiboRecurTail(25) wird die Antwort sofort angezeigt und es wird nur ein Anruf getätigt. Für FiboRecur(25) werden Tausende von Anrufen durchgeführt und es wird einige Sekunden lang ausgeführt, bevor das Ergebnis angezeigt wird.
Wir können auch die Laufzeiten mit der Funktion benchmark aus dem Paket rbenchmark :
Also, wenn R keine Tail-Rekursion unterstützt, was passiert in FiboRecurTail(25) , so dass es so schnell wie die iterative Version läuft, während die "naive" rekursive Funktion wie Melasse läuft? Ist es eher, dass R Tail-Rekursion unterstützt, aber nicht eine "naive" rekursive Version einer Funktion optimiert, um tail-call rekursiv zu sein, wie es andere Programmiersprachen (Haskell zum Beispiel) tun? Das verstehe ich aus diesem Post in der Mailingliste von R .
Ich würde es sehr schätzen, wenn jemand etwas Licht in diese Sache bringen würde. Danke!
Der Unterschied besteht darin, dass FiboRecur sich bei jeder Rekursion zweimal selbst aufruft. Innerhalb von FiboRecurTail , fib_help ruft sich nur einmal auf.
Damit haben Sie eine Menge mehr Funktionsaufrufe mit dem ersten. Im Falle von FiboRecurTail(25) haben Sie eine Rekursionstiefe von ~ 25 Calls. FiboRecur(25) führt zu 242.785 Funktionsaufrufen (einschließlich der ersten).
Ich habe keine der Routinen getaktet, aber beachte, dass du 0.00 für beide schnelleren Routinen zeigst. Sie sollten einen Unterschied mit einem höheren Eingabewert sehen, aber beachten Sie, dass Fibo genau so viel iteriert wie FiboRecurTail recurses.
Im rekursiven Ansatz naive haben Sie wiederholt viele Werte berechnet. Wenn Sie beispielsweise FiboRecur(30) berechnen, berechnen Sie FiboRecur(29) und FiboRecur(28) , und jeder dieser beiden Aufrufe ist unabhängig. Und in FiboRecur(29) berechnen Sie FiboRecur(28) erneut und FiboRecur(27) , obwohl FiboRecur(28) bereits anderswo berechnet wurde. Und dies geschieht für jede Phase der Rekursion. Oder einfach gesagt, für jeden Anstieg von n verdoppelt sich der Rechenaufwand fast, aber in der Realität sollte es einfach so einfach sein, wie die letzten zwei berechneten Zahlen zusammen zu addieren.
Eine kleine Zusammenfassung von FiboRecur(4) : FiboRecur(0) wird zweimal berechnet, FiboRecur(1) wird dreimal berechnet, FiboRecur(2) wird zweimal berechnet und FiboRecur(3) wird einmal berechnet. Die vorherigen drei sollten wirklich einmal berechnet und irgendwo gespeichert werden, damit Sie die Werte immer dann extrahieren können, wenn sie benötigt werden. Und deshalb sehen Sie so viele Funktionsaufrufe, obwohl es keine große Anzahl ist.
In der rekursiven Tail-Version werden jedoch alle zuvor berechneten Werte über a + b -Parameter an die nächste Stufe übergeben, was zahllose repetitive Berechnungen wie in der naiven rekursiven Version vermeidet und somit effizienter ist.