Wie sieht Ihr Lieblings-Sprache Griff tief die Rekursion?
Ich habe vor kurzem angefangen zu lernen, Python und ich war ziemlich überrascht, eine 1000 Tiefe der Rekursion beschränken (Standard). Wenn du es hoch genug ist, über 30000, stürzt mit einem segmentation fault genau wie C. Obwohl C zu gehen scheint, sehr viel höher.
(Die Python-Leute sind schnell darauf hin, dass Sie immer konvertieren rekursive Funktionen an iterativ sind und dass Sie immer schneller. Das ist 100% wahr. Es ist nicht wirklich was meine Frage ist, aber.)
Habe ich versucht, das gleiche experiment in Perl und irgendwo um die 10 Millionen rekursionen es verbraucht alle meine 4 gigs ram und ich benutzt ^C, um zu versuchen zu stoppen. Klar Perl nicht mit dem C-stack, aber es wird eine lächerliche Menge Speicher, wenn es eine Rekursion -- nicht sehr schockierend, wenn man bedenkt, wie viel Arbeit es zu tun hat, zum aufrufen von Funktionen.
Habe ich versucht, in der Hecht-und war völlig überrascht, 100,000,000 rekursionen in etwa 2 Sekunden. Ich habe keine Ahnung, wie er das Tat, aber ich vermute, dass es abgeflacht ist, die Rekursion zu einer iterativen Prozess -- es scheint nicht zu verbrauchen jede extra Speicher, während Sie es tut. [Hinweis: der Hecht hat flatten trivialen Fällen, aber segfaults auf mehr kompliziert, oder so bin ich gesagt.]
Verwendet habe ich diese ansonsten nutzlose Funktionen:
int f(int i, int l) { if(i<l) return f(i+1,l); return i; }
sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] };
def f(i,l):
if i<l:
return f(i+1,l)
return i
Ich bin sehr neugierig, wie andere Sprachen (z.B. PHP, Ruby, Java, Lua, Ocaml, Haskell) Griff Rekursion und warum Sie es behandeln, dass Art und Weise. Beachten Sie bitte außerdem, ob es einen Unterschied macht, ob die Funktion "tail-recursive" (siehe Kommentar).
- Dein Beispiel ist tail-rekursiv ist, also jede Sprache, Implementierung, unterstützt tail-Rekursion effektiv transformieren der rekursive Aufruf in einem "goto".
Du musst angemeldet sein, um einen Kommentar abzugeben.
"Die Python-Leute sind schnell darauf hin, dass man immer konvertieren, Funktionen rekursiv auf iterativ entwickelten und dass Sie sich immer schneller"
Dies ist wahr, aber wenn es wirklich so einfach, wie alle, die, warum nicht in Python, das für mich tun, damit mein code Aussehen kann so einfach wie möglich? (Ich sage dies nicht, um slam-Python-Implementierung, aber da die Antwort das problem erklärt).
Rekursion Optimierungen im funktionalen Sprachen, da, wie die, dem 14 Jahrhundert oder so etwas. Haskell, CAML, Lisp-Implementierungen alle in der Regel konvertieren, zumindest tail-rekursive Funktionen Iterationen: dass Sie im Grunde tun dies, indem Sie entdecken, dass es möglich ist, d.h., dass die Funktion umgestellt werden kann, so dass keine lokale Variablen anderer als der Rückgabe-Wert verwendet werden, nach dem rekursiven Aufruf. Ein trick, um es möglich zu machen, wenn es einige Arbeit, um die recursed return Wert vor der Rückkehr, ist die Einführung eines zusätzlichen "Akku" - parameter. In einfachen Worten bedeutet dies, die Arbeit effektiv getan auf dem Weg "nach unten", anstatt auf dem Weg "nach oben": die Suche rund um für "wie man eine Funktion tail-rekursiv" für weitere details.
Die tatsächlichen details, aus einem tail-rekursive Funktion in einer Schleife ist im Grunde zu jigger mit Ihrem Aufruf-Konvention Z Sie können "ausführen der Anruf" einfach durch einstellen der Parameter und springen zurück zum Anfang der Funktion, ohne sich die Mühe zu sparen alle, die in Sachen Umfang, dass Sie wissen, dass Sie nie verwenden werden. In assembler Bedingungen, die Sie nicht beibehalten möchten, caller-saves Register, wenn Daten-flow-Analyse sagt Ihnen, Sie sind ungenutzt über den Ruf, und das gleiche gilt für alles auf dem stack: du musst dich nicht bewegen Sie den stack-pointer auf einen Anruf, wenn Sie nichts dagegen haben "Ihre" bit-der stack wird kritzelte über die von der nächsten Rekursion/iteration.
Entgegen, wie Sie paraphrasiert die Python-Leute, die Umwandlung eine allgemein rekursive Funktion mit einer iteration ist nicht trivial: zum Beispiel, wenn es mehrfach rekursive dann in einem einfachen Ansatz, Sie müssen noch einen Stapel.
Memoization ist eine nützliche Technik, aber, für beliebig rekursive Funktionen, die Sie vielleicht gerne sehen, wenn Sie interessiert sind, in der mögliche Ansätze. Was es bedeutet ist, dass jedes mal, wenn eine Funktion ausgewertet wird, Sie halten das Ergebnis in einem cache. Um diese zu verwenden, zu optimieren, Rekursion, im Grunde, wenn Ihre rekursiven Funktion zählt "down", und Sie memoize, dann können Sie es zu bewerten iterativ durch hinzufügen einer Schleife, die zählt "up" - Berechnung wird jeder Wert der Funktion in drehen Sie, bis Sie das Ziel erreichen. Dieser verbraucht sehr wenig stack-Speicher zur Verfügung gestellt, dass die memo-cache ist groß genug, um alle die Werte, die Sie brauchen: zum Beispiel, wenn f(n) hängt von f(n-1), f(n-2) und f(n-3) benötigen Sie nur Platz für 3 Werte im cache: wie Sie gehen, bis Sie kicken können die Leiter Weg. Wenn f(n) hängt von f(n-1) und f(n/2), Sie brauchen viel Platz im cache, aber immer noch weniger als Sie verwenden würden, für Stapel in einer unoptimised Rekursion.
Dies ist eher eine Umsetzung in Frage als eine Sprache in Frage. Es gibt nichts zu stoppen einige (stoopid) C-compiler-Implementierung auch aus der Begrenzung der call-stack auf 1000. Es gibt eine Menge von kleinen Prozessoren gibt, die nicht Stapelspeicher für auch dass viele.
Vielleicht werden Sie sagen, dass, aber das ist nicht ganz korrekt. Rekursion kann immer umgewandelt werden iteration, aber manchmal ist es auch erfordert die manuelle Verwendung einer stack zu. In diesen Umständen, ich konnte sehen, dass die rekursive version schneller (vorausgesetzt, Sie sind intelligent genug, um einfache Optimierungen, wie ziehen Sie nicht benötigte Deklarationen außerhalb des rekursiven routine). Nachdem alle, die Stapel schiebt umliegenden procedure calls sind ein gut eingegrenztes problem, dass Ihr compiler sollte wissen, wie zu optimieren sehr gut. Handbuch stack-Operationen, auf der anderen Seite, sind nicht zu spezialisierten code-Optimierung in den compiler, und haften für alle Arten von Benutzer-interface-Plausibilitätsprüfungen, dass es dauern wird, bis zusätzliche Zyklen.
Kann es sein, dass der iterative - /stack-Lösung ist immer schneller in Python. Wenn ja, ist das ein Versagen der Python, nicht der Rekursion.
PHP hat ein default-limit von 100, bevor es stirbt:
Fatal error: Maximum function nesting level of '100' reached, aborting!
Bearbeiten: Sie können ändern Sie den Grenzwert mit
ini_set('xdebug.max_nesting_level', 100000);
, aber wenn man oben über 1150 Iterationen PHP abstürzt:[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.
C#/.NET verwenden tail-Rekursion in einer bestimmten Reihe von Umständen. (Der C# - compiler nicht emittieren eine tailcall opcode, aber die JIT implementieren tail recursion in einigen Fällen.
Shri Borde hat auch einen Beitrag zu diesem Thema. Natürlich, die CLR wird laufend verändert, und mit .NET 3.5 und 3.5SP1 es mag sich geändert haben, wieder mit Bezug auf tail-calls.
Mithilfe der folgenden in der F# - interactive-Konsole, es lief in weniger als einer Sekunde:
Dann habe ich versucht, eine gerade übersetzung, d.h.
Gleichen Ergebnis, aber unterschiedlicher Zusammenstellung.
Dies ist, was f sieht aus wie in bei der übersetzung in C#:
g, jedoch ist übersetzt dies:
Es ist interessant, dass zwei Funktionen, sind grundlegend die gleichen sind Verschieden gerendert, die von der F# - compiler. Es zeigt auch, dass der F# - compiler tail-rekursive Optimierung. Somit sollte diese Schleife, bis ich erreicht das limit für 32-bit-Ganzzahlen.
Laut diesem thread, rund 5,000,000 mit java, 1Gb RAM. (und dass, mit den 'client' version des hotspot)
Wurde mit einem stack (-Xss) von 300Mo.
Mit einem -server-option, dass erhöht werden konnte.
Kann man auch versuchen, optimieren der compiler (mit JET zum Beispiel) zu reduzieren, die stack-overhead auf jeder Ebene.
In einigen nicht-pathologische Fälle (wie deinen), (neuesten) Lua verwenden tail call recursion, dh. es wird einfach springen, ohne pushen von Daten im stack. So ist die Zahl der Rekursion Schleifen können fast unbegrenzt.
Getestet mit:
Auch mit:
und sogar versucht, cross-Rekursion (f ruft g und g ruft f...).
Unter Windows, Lua 5.1 benutzt um 1.1 MB (konstant) ausführen, endet in wenigen Sekunden.
Laufenden ruby-1.9.2-dev (2010-07-11 revision 28618) [x86_64-darwin10.0.0] auf eine ältere weiße macbook:
Ausgaben 9353 für mich, was bedeutet Ruby Würfelspiel mit weniger als 10.000 Aufrufe auf den stack.
Mit cross-Rekursion, wie:
er scheißt in der Hälfte der Zeit, die auf 4677 (~= 9353 /2).
Kann ich squeeze-out ein paar mehr Iterationen durch das einwickeln der rekursive Aufruf in einer proc:
welche bekommt bis zu 4850 vor erroring.
Visual Dataflex wird stack-überlauf.
Ich bin durchaus ein fan der funktionalen Programmierung, und da die meisten dieser Sprachen implementieren tail-call-Optimierung, können Sie recurse so viel, wie Sie möchten 😛
Jedoch praktisch, ich habe eine Menge von Java-und Python verwenden auch eine Menge. Keine Ahnung, was begrenzen Java hat, aber für Python ich hatte eigentlich geplant (aber noch nicht gemacht) zu implementieren, Dekorateur, die würden tail-call-Optimierung der eingerichteten Funktion.
Ich plante, diese nicht zu optimieren Rekursion, sondern hauptsächlich als eine übung in dynamisch patchen Python-bytecode und das lernen mehr über Pythons-Interna.
Heres einige itneresting links: http://lambda-the-ultimate.org/node/1331 und http://www.rowehl.com/blog/?p=626
Es ist ein Weg, um zu verbessern auf der
Perl
code zu machen, verwenden Sie eine Konstante Größe stapeln. Sie tun dies durch die Verwendung einer speziellen form vongoto
.Beim ersten Aufruf wird Speicherplatz auf dem stack. Dann ändert es seine Argumente, und starten Sie das Unterprogramm auf, ohne etwas mehr auf den Stapel. Es wird daher behaupten, dass es nie aufgerufen, Ihre selbst, ändern Sie es in ein iterativer Prozess.
Konnte man auch mit dem Betreff::Aufruf::Wiederkehren Modul. Das macht den code leichter zu verstehen und kürzer.
clojure stellt eine spezielle form für die tail-Rekursion "wiederkehren" dies kann nur verwendet werden in der Rute-Orte der ast. Ansonsten verhält es sich wie bei java und wird wahrscheinlich werfen Sie einen StackverflowException.