Wie hoch ist die maximale Rekursionstiefe in Python und wie erhöht man sie?
Habe ich diese tail-rekursive Funktion hier:
def fib(n, sum):
if n < 1:
return sum
else:
return fib(n-1, sum+n)
c = 998
print(fib(c, 0))
Es funktioniert bis n=997, dann einfach bricht und spuckt eine "maximale Rekursionstiefe überschritten im Vergleich" RuntimeError
. Ist das nur ein stack-overflow? Gibt es eine Möglichkeit dies zu umgehen?
Kommentar zu dem Problem - Öffnen
Siehe auch stackoverflow.com/questions/5061582/...
memoization beschleunigen könnten Ihre Funktion und erhöhen Sie Ihre effektive rekursiven Tiefe, indem Sie die zuvor berechneten Werte zu beenden, anstatt die Erhöhung der stack-Größe.
Nur aus Neugier, warum hast du die Namen dieser
fib
? Waren, die Sie beabsichtigen zu verwenden, diese als Helfer zur Berechnung der Fibonacci-Folge? Wenn ja, was ist Ihr Ansatz? InformationsquelleAutor der Frage quantumSoup | 2010-07-23
Du musst angemeldet sein, um einen Kommentar abzugeben.
Es ist ein Schutz gegen ein stack-überlauf, ja. Python (oder besser gesagt, der CPython-Implementierung) nicht optimieren, tail recursion, und der ungezügelten Rekursion verursacht stack-overflows. Sie können ändern Sie die Rekursion Grenze mit
sys.setrecursionlimit
, aber das ist gefährlich-die standard-Grenze ist ein wenig konservativ, aber Python stackframes werden können Recht groß ist.Python ist nicht eine funktionale Sprache und tail-Rekursion ist nicht eine besonders effiziente Technik. Das umschreiben der Algorithmus iterativ, wenn möglich, ist in der Regel eine bessere Idee.
InformationsquelleAutor der Antwort Thomas Wouters
Sieht aus wie Sie gerade benötigen, um eine höhere Rekursionstiefe
InformationsquelleAutor der Antwort David Young
Es ist zu vermeiden, wurde ein Pufferüberlauf gefunden. Der Python-interpreter die Grenzen der Tiefe der Rekursion zur Vermeidung unendlicher rekursionen, wodurch die stack-überlauf.
Versuchen Sie die Erhöhung der Rekursion Grenze (sys.setrecursionlimit) oder re-schreiben Sie Ihren code ohne Rekursion.
vom python-website:
InformationsquelleAutor der Antwort Scharron
Eine Sprache verwenden, die garantiert der tail-call-Optimierung. Oder verwenden Sie die iteration. Alternativ Holen Sie sich cute mit Dekoratoren.
InformationsquelleAutor der Antwort Marcelo Cantos
Ich weiß, das ist eine alte Frage, aber für diejenigen, die das Lesen, würde ich empfehlen gegen die Verwendung von Rekursion für Probleme wie diese - Listen sind viel schneller und vermeiden Sie Rekursion vollständig. Würde ich dies umsetzen, wie:
(Bei der Verwendung von n+1 in xrange, wenn Sie anfangen zu zählen deine fibonacci-Folge, von 0 statt von 1.)
InformationsquelleAutor der Antwort Daniel
Natürlich Fibonacci-zahlen berechnet werden können in O(n) durch die Anwendung der Binet-Formel:
Als die Kommentatoren Hinweis: es ist nicht O(1) sondern O(n) wegen
2**n
. Auch ein Unterschied ist, dass Sie nur noch einen Wert, während mit Rekursion erhalten Sie alle Werte derFibonacci(n)
bis zu diesem Wert.InformationsquelleAutor der Antwort rwst
Ich hatte ein ähnliches Problem mit der Fehlermeldung "Maximale Rekursionstiefe überschritten". Ich entdeckte, war der Fehler wird ausgelöst durch eine beschädigte Datei in dem Verzeichnis, ich war looping über und über mit os.Fuss. Wenn Sie Probleme haben, die Lösung zu diesem Problem und Sie arbeiten mit Dateipfaden, sicher sein, es zu beschränken, wie es könnte eine korrupte Datei.
InformationsquelleAutor der Antwort Tyler
Anwendung von Generatoren?
oben fib () - Funktion angepasst von: http://intermediatepythonista.com/python-generators
InformationsquelleAutor der Antwort alex
resource.setrlimit
muss auch verwendet werden, zur Erhöhung der stack-Größe und verhindern, dass segfaultDen Linux-kernel Grenzen der stack von Prozessen.
Python speichert lokale Variablen auf dem stack des interpreters, und so die Rekursion nimmt Stapelspeicher des interpreters.
Wenn der Python-interpreter versucht zu gehen, über das stack-limit, der Linux-kernel segfaults.
Dem stack-limit-Größe gesteuert wird mit der
getrlimit
undsetrlimit
system fordert.Python bietet Zugang zu den system calls durch den
resource
Modul.Natürlich, wenn Sie halten die Erhöhung für ulimit, dein RAM wird laufen, die entweder Ihren computer verlangsamen, zu einem Stillstand aufgrund von swap-Wahnsinn, oder töten Python über die OOM-Killer.
Aus der bash können Sie sehen, und legen Sie das stack-limit (in kb) mit:
Default-Wert für mich ist 8Mb.
Siehe auch:
Getestet auf Ubuntu 16.10, Python 2.7.12.
InformationsquelleAutor der Antwort Ciro Santilli 包子露宪 六四事件 法轮功
Als @alex vorgeschlagen, könnte man eine generator-Funktion, dies zu tun. Hier ist das äquivalent der code in deiner Frage:
InformationsquelleAutor der Antwort martineau
Viele empfehlen, dass die Erhöhung der Rekursion beschränken, ist eine gute Lösung, allerdings ist es nicht, denn es gibt immer limit. Stattdessen verwenden Sie eine iterative Lösung.
InformationsquelleAutor der Antwort Harun Ergül
Wenn Sie möchten, um nur einige Fibonacci-zahlen, können Sie verwenden, matrix-Methode.
Es ist schneller als numpy verwendet die schnelle Potenzierung Algorithmus. Sie erhalten Antwort in O(log n). Und es ist besser als die Binet-Formel, weil es verwendet nur ganze zahlen. Aber wenn Sie wollen alle Fibonacci-zahlen bis n ist, dann ist es besser, es zu tun durch Auswendiglernen.
InformationsquelleAutor der Antwort bebidek
Wenn Sie oft ändern müssen, die Rekursion begrenzen (z.B. während der Programmierung der Lösung des puzzles) können Sie definieren eine einfache Kontext-manager wie diese:
Dann eine Funktion aufrufen, die eine benutzerdefinierte Grenze, die Sie tun können:
Auf die Ausfahrt aus dem Körper des
with
Anweisung der rekursions-Grenze wird auf den Standardwert zurückgesetzt.InformationsquelleAutor der Antwort Eugene Yarmash