Was ist die maximale Rekursionstiefe in Python und wie man es erhöht?

Ich habe diese Schwanz 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 zu n = 997, dann bricht es einfach und spuckt eine "maximale Rekursionstiefe überschritten im Vergleich" RuntimeError . Ist das nur ein Stapelüberlauf? Gibt es einen Weg, um es zu umgehen?

10 Solutions collect form web for “Was ist die maximale Rekursionstiefe in Python und wie man es erhöht?”

Es ist ein Wächter gegen einen Stapelüberlauf, ja. Python (oder vielmehr die CPython-Implementierung) optimiert die Schwanzrekursion nicht, und die ungezügelte Rekursion verursacht Stapelüberläufe. Sie können die Rekursionsgrenze mit sys.setrecursionlimit , aber das ist gefährlich – die Standardgrenze ist ein wenig konservativ, aber Python Stackframes kann ziemlich groß sein.

Python ist keine funktionale Sprache und Schwanz Rekursion ist nicht eine besonders effiziente Technik. Umschreiben des Algorithmus iterativ, wenn möglich, ist in der Regel eine bessere Idee.

Sieht aus wie Sie nur eine höhere Rekursionstiefe einstellen müssen

 sys.setrecursionlimit(1500) 

Es ist ein Stapelüberlauf zu vermeiden. Der Python-Interpreter begrenzt die Tiefen der Rekursion, um Ihnen zu helfen, unendliche Rekursionen zu vermeiden, was zu Stacküberläufen führt. Versuchen Sie, die Rekursionsgrenze (sys.setrecursionlimit) zu erhöhen oder Ihren Code ohne Rekursion neu zu schreiben.

Von python website :

sys.getrecursionlimit()

Geben Sie den aktuellen Wert der Rekursionsgrenze, die maximale Tiefe des Python-Interpreter-Stacks zurück. Diese Grenze verhindert, dass unendliche Rekursion einen Überlauf des C-Stacks verursacht und Python abstürzt. Es kann durch setrecursionlimit () eingestellt werden.

Verwenden Sie eine Sprache, die eine Tail-Call-Optimierung garantiert. Oder Iteration verwenden. Alternativ, niedlich mit Dekorateure .

Ich weiß, das ist eine alte Frage, aber für die Lesung, würde ich empfehlen, gegen die Rekursion für Probleme wie diese – Listen sind viel schneller und vermeiden Rekursion ganz. Ich würde dies als:

 def fibonacci(n): f = [0,1,1] for i in xrange(3,n): f.append(f[i-1] + f[i-2]) return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1]) 

(Verwenden Sie n + 1 in xrange, wenn Sie beginnen, Ihre Fibonacci-Sequenz von 0 anstelle von 1 zu zählen)

Natürlich können Fibonacci-Zahlen in O (1) durch Anwendung der Binet-Formel berechnet werden:

 from math import floor, sqrt def fib(n): return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5)) 

Du brauchst große ganze Zahlen von numpy, wenn die Ergebnisse nicht mehr in eine lange passen.

Ich hatte ein ähnliches Problem mit dem Fehler "Max Rekursionstiefe überschritten". Ich entdeckte, dass der Fehler durch eine korrupte Datei im Verzeichnis ausgelöst wurde, mit dem ich mit os.walk überging. Wenn Sie Probleme haben, dieses Problem zu lösen, und Sie arbeiten mit Dateipfaden, achten Sie darauf, es zu verengen, da es sich um eine beschädigte Datei handelt.

Verwenden Sie Generatoren?

 def fib(): a, b = 0, 1 while True: yield a a, b = b, a + b fibs = fib() #seems to be the only way to get the following line to work is to #assign the infinite generator to a variable f = [fibs.next() for x in xrange(1001)] for num in f: print num 

Oben fib () Funktion angepasst von: http://intermediatepythonista.com/pythongeneratoren

Viele empfehlen, dass die zunehmende Rekursionsgrenze eine gute Lösung ist, aber es ist nicht, weil es immer begrenzt wird. Verwenden Sie stattdessen eine iterative Lösung.

 def fib(n): a,b = 1,1 for i in range(n-1): a,b = b,a+b return a print fib(5) 

resource.setrlimit muss auch verwendet werden, um die Stackgröße zu erhöhen und segfault zu verhindern

Der Linux-Kernel begrenzt den Prozessstapel.

Rekursion nimmt Stapelplatz auf.

Wenn Python versucht, über die Stack-Grenze zu gehen, wird der Linux-Kernel segfaults es.

Die getrlimit wird mit den getrlimit und setrlimit Systemaufrufen gesteuert.

Python bietet Zugriff auf diese Systemaufrufe über das resource .

 import resource import sys print resource.getrlimit(resource.RLIMIT_STACK) print sys.getrecursionlimit() print # Will segfault without this line. resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY]) sys.setrecursionlimit(0x100000) def f(i): print i sys.stdout.flush() f(i + 1) f(0) 

Natürlich, wenn du immer weiter steigst, wird dein RAM auslaufen, was entweder deinen Computer zum Stillstand bringt, weil er den Wahnsinn tauscht oder Python über den OOM Killer tötet.

Von bash, können Sie sehen und setzen Sie die Stack-Grenze (in kb) mit:

 ulimit -s ulimit -s 10000 

Der Standardwert für mich ist 8Mb.

Siehe auch:

  • Einstellen der Stapelung in einem Python-Skript
  • Python: Was ist die harte Rekursionsgrenze für Linux, Mac und Windows?

Getestet auf Ubuntu 16.10, Python 2.7.12.

  • Rekursionsfunktion funktioniert nicht richtig
  • Rekursiv dekrementieren eine Liste durch 1
  • N-Queen-Backtracking in Python: Wie gibt man Lösungen zurück, anstatt sie zu drucken?
  • Python rekursiv anhängen Liste Funktion
  • Das max-Element in einer Sequenz mit Rekursion zu finden
  • Rekursionsfunktion in Python
  • Warum gibt meine rekursive Funktion keine?
  • Python recursion return Keine Typ
  • Rekursiver Generator zum Abflachen von verschachtelten Listen
  • Lock-Kombinationen für dynamische Sperrgröße
  • Python-Rekursions- und return-Anweisungen
  • Python ist die beste Programmiersprache der Welt.