Was ist die maximale Rekursionstiefe in Python und wie kann sie erhöht werden?

420

Ich habe diese rekursive Schwanzfunktion hier:

def recursive_function(n, sum):
    if n < 1:
        return sum
    else:
        return recursive_function(n-1, sum+n)

c = 998
print(recursive_function(c, 0))

Es funktioniert bis n=997, dann bricht es einfach und spuckt a aus RecursionError: maximum recursion depth exceeded in comparison. Ist das nur ein Stapelüberlauf? Gibt es eine Möglichkeit, das zu umgehen?

quantumSoup
quelle
3
Siehe auch stackoverflow.com/questions/5061582/…
Thomas Ahle
8
Das Speichern kann Ihre Funktion beschleunigen und die effektive rekursive Tiefe erhöhen, indem zuvor berechnete Werte beendet werden, anstatt die Stapelgröße zu erhöhen.
Cyoce
2
Die Rekursionsgrenze ist normalerweise 1000.
Boris
1
@tonix Der Interpreter fügt einen Stack-Frame hinzu (die line <n>, in <module>In-Stack-Traces) und dieser Code benötigt 2 Stack-Frames n=1(da der Basisfall so ist n < 1, dass n=1er immer noch wiederholt wird). Und ich denke, das Rekursionslimit ist nicht inklusive, wie in "Fehler, wenn Sie 1000 treffen", nicht "Fehler, wenn Sie 1000 (1001) überschreiten". 997 + 2ist weniger als 1000, also funktioniert 998 + 2es nicht, weil es das Limit erreicht.
Boris
1
@tonix no. recursive_function(997)funktioniert, es bricht bei 998. Wenn Sie es aufrufen recursive_function(998), werden 999 Stack-Frames verwendet und 1 Frame wird vom Interpreter hinzugefügt (da Ihr Code immer so ausgeführt wird, als ob er Teil des Top-Level-Moduls ist), wodurch das 1000-Limit erreicht wird.
Boris

Antworten:

468

Es ist ein Schutz gegen einen Stapelüberlauf, ja. Python (oder besser gesagt die CPython-Implementierung) optimiert die Schwanzrekursion nicht, und eine ungezügelte Rekursion führt zu Stapelüberläufen. Sie können das Rekursionslimit mit überprüfen und das Rekursionslimit mit sys.getrecursionlimitändern sys.setrecursionlimit, dies ist jedoch gefährlich - das Standardlimit ist ein wenig konservativ, aber Python-Stackframes können ziemlich groß sein.

Python ist keine funktionale Sprache und die Schwanzrekursion ist keine besonders effiziente Technik. Wenn möglich, ist es im Allgemeinen besser, den Algorithmus iterativ umzuschreiben.

Thomas Wouters
quelle
4
Nach meiner Erfahrung müssen Sie das Limit sowohl in sysden resourceModulen als auch in den Modulen erhöhen
Thomas Ahle
3
Als Taktik, um es in eine iterative Version umzuwandeln, könnte ein Tail Call Optimization Decorator verwendet werden
jfs
3
Sie können svn.python.org/projects/python/trunk/Tools/scripts/… verwenden , um Ihre Betriebssystemobergrenze herauszufinden
Ullullu
8
Für diejenigen, die an der Quelle interessiert sind, ist das Standard-Rekursionslimit auf 1000 hg.python.org/cpython/file/tip/Python/ceval.c#l691 festgelegt und kann mithilfe der API unter hg.python.org/cpython geändert werden /file/tip/Python/sysmodule.c#l643, was wiederum das Limit auf den neuen Wert unter hg.python.org/cpython/file/tip/Python/ceval.c#l703 setzt
Pramod
16
Die Schwanzrekursion ist eine perfekt effiziente Technik in einer dafür optimierten Programmiersprache. Für die richtige Art von Problem kann es eine aussagekräftigere und iterativere Implementierung sein. Die Antwort bedeutet wahrscheinlich "speziell in Python", aber das steht nicht darauf
Peter R
135

Sieht so aus, als müssten Sie nur eine höhere Rekursionstiefe festlegen :

import sys
sys.setrecursionlimit(1500)
David Young
quelle
In meinem Fall habe ich die return-Anweisung im Basisfall vergessen und sie hat 1000 überschritten. Python hat diese Ausnahme ausgelöst und ich war erstaunt, weil ich mir über die Nr. Sicher war. von Stapeln wird es erstellt, um es auszuführen.
Vijayraj34
sys.setrecursionlimit (50) oder ein kleiner Betrag ist nützlich, wenn Ihr Programm eine Rekursion eingibt und Sie möchten, dass die Fehlermeldung NICHT Seiten und Seiten desselben Textes enthält. Ich fand dies sehr hilfreich beim Debuggen von (meinem) fehlerhaften rekursiven Code.
Peawormsworth
56

Dies dient dazu, einen Stapelüberlauf zu vermeiden. Der Python-Interpreter begrenzt die Rekursionstiefe, um unendliche Rekursionen zu vermeiden, die zu Stapelüberläufen führen. Versuchen Sie, das Rekursionslimit ( sys.setrecursionlimit) zu erhöhen oder Ihren Code ohne Rekursion neu zu schreiben.

Aus der Python-Dokumentation :

sys.getrecursionlimit()

Gibt den aktuellen Wert des Rekursionslimits zurück, die maximale Tiefe des Python-Interpreter-Stacks. Diese Begrenzung verhindert, dass eine unendliche Rekursion einen Überlauf des C-Stapels verursacht und Python zum Absturz bringt. Es kann von eingestellt werden setrecursionlimit().

Scharron
quelle
Auf meinem Anaconda x64, 3.5 Python unter Windows ist das Standardlimit 1000.
Guillaume Chevalier
30

Wenn Sie das Rekursionslimit häufig ändern müssen (z. B. beim Lösen von Programmierrätseln), können Sie einen einfachen Kontextmanager wie folgt definieren :

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit
        self.old_limit = sys.getrecursionlimit()

    def __enter__(self):
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

Um eine Funktion mit einem benutzerdefinierten Limit aufzurufen, können Sie Folgendes tun:

with recursionlimit(1500):
    print(fib(1000, 0))

Beim Verlassen des Hauptteils der withAnweisung wird das Rekursionslimit auf den Standardwert zurückgesetzt.

Eugene Yarmash
quelle
Sie möchten auch das Rekursionslimit des Prozesses mit erhöhenresource . Ohne diesen Fehler wird ein Segmentierungsfehler angezeigt, und der gesamte Python-Prozess stürzt ab, wenn Sie setrecursionlimitzu hoch sind und versuchen, das neue Limit zu verwenden (ca. 8 Megabyte Stapelrahmen, was mit der oben beschriebenen einfachen Funktion ~ 30.000 Stapelrahmen bedeutet) mein Laptop).
Boris
16

Verwenden Sie eine Sprache, die eine Tail-Call-Optimierung garantiert. Oder verwenden Sie die Iteration. Alternativ können Sie auch mit Dekorateuren süß werden .

Marcelo Cantos
quelle
36
Das wirft das Baby eher mit dem Badewasser raus.
Russell Borogove
3
@ Russell: Nur eine der von mir angebotenen Optionen empfiehlt dies.
Marcelo Cantos
"Werde süß mit Dekorateuren" ist nicht gerade eine Option.
Herr B
@ Mr.B, es sei denn, Sie benötigen mehr als Stapelrahmenulimit -s , ja, es ist stackoverflow.com/a/50120316
Boris
14

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

Der Linux-Kernel begrenzt den Stapel von Prozessen .

Python speichert lokale Variablen auf dem Stapel des Interpreters, sodass die Rekursion den Stapelspeicher des Interpreters beansprucht.

Wenn der Python-Interpreter versucht, das Stapellimit zu überschreiten, macht der Linux-Kernel einen Segmentierungsfehler.

Die Stapelbegrenzungsgröße wird mit den Systemaufrufen getrlimitund setrlimitgesteuert.

Python bietet über das resourceModul Zugriff auf diese Systemaufrufe .

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)

Wenn Sie das Ulimit weiter erhöhen, wird Ihr RAM natürlich knapp, was entweder Ihren Computer aufgrund von Swap-Wahnsinn zum Stillstand bringt oder Python über den OOM Killer tötet.

In Bash können Sie das Stapellimit (in KB) anzeigen und festlegen mit:

ulimit -s
ulimit -s 10000

Der Standardwert für mich ist 8 MB.

Siehe auch:

Getestet unter Ubuntu 16.10, Python 2.7.12.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
quelle
1
Der Versuch, rlimit_stacknach Stack Clash- Korrekturen eine Einstellung vorzunehmen, kann zu Fehlern oder damit verbundenen Problemen führen. Siehe auch Red Hat Ausgabe 1463241
jww
Ich habe diesen (den Python-Ressourcenteil) verwendet, um meine Implementierung des Kosaraju-Algorithmus für den mittleren (riesigen) Datensatz von Professor Tim Roughgarden zu unterstützen. Meine Implementierung funktionierte mit kleinen Mengen, sicherlich war das Problem mit einem großen Datensatz das Rekursions- / Stapellimit ... Oder war es das? Ja, das war es! Vielen Dank!
Nilo
9

Mir ist klar, dass dies eine alte Frage ist, aber für diejenigen, die lesen, würde ich empfehlen, bei Problemen wie diesen keine Rekursion zu verwenden - Listen sind viel schneller und vermeiden Rekursion vollständig. Ich würde dies implementieren 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 Ihre Fibonacci-Sequenz von 0 statt 1 zählen.)

Daniel
quelle
13
Warum O (n) verwenden, wenn Sie O (1) verwenden können?
Janus Troelsen
11
Nur für den Fall, dass der Kommentar zum O (n) -Raum verwirrend war: Verwenden Sie keine Liste. List behält alle Werte bei, wenn Sie nur den n-ten Wert benötigen. Ein einfacher Algorithmus wäre, die letzten beiden Fibonacci-Zahlen beizubehalten und hinzuzufügen, bis Sie die gewünschte erhalten. Es gibt auch bessere Algorithmen.
Milimetric
3
@ Mathime: xrangeheißt einfach range, in Python 3.
Eric O Lebigot
1
@EOL Ich bin mir dessen bewusst
Mathime
7
@Mathime Ich habe die Dinge für diejenigen, die diese Kommentare lesen, explizit gemacht.
Eric O Lebigot
9

Natürlich können Fibonacci-Zahlen in O (n) unter 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))

Wie die Kommentatoren bemerken, ist es nicht O (1), sondern O (n) wegen 2**n. Ein Unterschied besteht auch darin, dass Sie nur einen Wert erhalten, während Sie bei der Rekursion alle Werte Fibonacci(n)bis zu diesem Wert erhalten.

rwst
quelle
8
In Python gibt es keine maximale Größe eines Longs.
pppery
8
Es ist erwähnenswert, dass dies naufgrund von Gleitkomma-Ungenauigkeiten bei größeren Fehlern fehlschlägt - der Unterschied zwischen (1+sqrt(5))**nund (1+sqrt(5))**(n+1)wird kleiner als 1 ulp, sodass Sie falsche Ergebnisse erhalten.
2
Es gibt tatsächlich keine großen ganzen Zahlen in NumPy…
Eric O Lebigot
@ Mego Was? Es ist der Unterschied zwischen (1+sqrt(5))**nund ((1+sqrt(5))**n)+1das wird weniger als 1 ulp! (kleiner Tippfehler) Auch {@} rwst Das ist nicht O (1)! Die Berechnung 2**ndauert mindestens O (n).
user202729
3
@ user202729 Das stimmt nicht, die Berechnung 2**nist effektiv O (log (n)) unter Verwendung der Exponentiattion durch Quadrieren .
Sam
6

Ich hatte ein ähnliches Problem mit dem Fehler "Maximale Rekursionstiefe überschritten". Ich habe festgestellt, dass der Fehler durch eine beschädigte Datei in dem Verzeichnis ausgelöst wurde, mit dem ich eine Schleife durchgeführt habe os.walk. Wenn Sie Probleme bei der Lösung dieses Problems haben und mit Dateipfaden arbeiten, sollten Sie es eingrenzen, da es sich möglicherweise um eine beschädigte Datei handelt.

Tyler
quelle
2
Das OP gibt seinen Code an und sein Experiment ist nach Belieben reproduzierbar. Es handelt sich nicht um beschädigte Dateien.
T. Verron
5
Sie haben Recht, aber meine Antwort ist nicht auf das OP ausgerichtet, da dies vor über vier Jahren war. Meine Antwort zielt darauf ab, Menschen mit MRD-Fehlern zu helfen, die indirekt durch beschädigte Dateien verursacht werden - da dies eines der ersten Suchergebnisse ist. Es hat jemandem geholfen, da es gewählt wurde. Danke für die Abstimmung.
Tyler
2
Dies war das einzige, was ich bei der Suche nach meinem Problem gefunden habe, das einen Traceback mit "maximaler Rekursionstiefe" mit einer beschädigten Datei verbunden hat. Vielen Dank!
Jeff
5

Wenn Sie nur wenige Fibonacci-Zahlen erhalten möchten, können Sie die Matrixmethode verwenden.

from numpy import matrix

def fib(n):
    return (matrix('0 1; 1 1', dtype='object') ** n).item(1)

Es ist schnell, da numpy einen schnellen Exponentiationsalgorithmus verwendet. Sie erhalten eine Antwort in O (log n). Und es ist besser als Binets Formel, weil es nur ganze Zahlen verwendet. Wenn Sie jedoch alle Fibonacci-Zahlen bis zu n möchten, ist es besser, dies durch Auswendiglernen zu tun.

bebidek
quelle
Leider können Sie Numpy in den meisten wettbewerbsfähigen Programmierrichtern nicht verwenden. Aber ja, Sir, Ihre Lösung ist meine Lieblingslösung. Ich habe die Matrixlösung für einige Probleme verwendet. Dies ist die beste Lösung, wenn Sie eine sehr große Fibonacci-Zahl benötigen und keinen Modul verwenden können. Wenn Sie einen Modul verwenden dürfen, ist die Pisano-Periode der bessere Weg, dies zu tun.
Mentatkgs
4

Generatoren verwenden?

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

über fib () Funktion angepasst von: http://intermediatepythonista.com/python-generators

Alex
quelle
1
Der Grund dafür, dass einer Variablen ein Generator zugewiesen werden muss, liegt [fibs().next() for ...]darin, dass jedes Mal ein neuer Generator erstellt wird.
Tox123
2

Viele empfehlen, dass das Erhöhen des Rekursionslimits eine gute Lösung ist, jedoch nicht, weil es immer ein Limit gibt. 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)
Harun ERGUL
quelle
2

Wie von @alex vorgeschlagen , können Sie eine Generatorfunktion verwenden , um dies nacheinander anstatt rekursiv durchzuführen .

Hier ist das Äquivalent des Codes in Ihrer Frage:

def fib(n):
    def fibseq(n):
        """ Iteratively return the first n Fibonacci numbers, starting from 0. """
        a, b = 0, 1
        for _ in xrange(n):
            yield a
            a, b = b, a + b

    return sum(v for v in fibseq(n))

print format(fib(100000), ',d')  # -> no recursion depth error
Martineau
quelle
1

Ich wollte Ihnen ein Beispiel für die Verwendung der Memoisierung zur Berechnung von Fibonacci geben, da Sie auf diese Weise mithilfe der Rekursion erheblich größere Zahlen berechnen können:

cache = {}
def fib_dp(n):
    if n in cache:
        return cache[n]
    if n == 0: return 0
    elif n == 1: return 1
    else:
        value = fib_dp(n-1) + fib_dp(n-2)
    cache[n] = value
    return value

print(fib_dp(998))

Dies ist immer noch rekursiv, verwendet jedoch eine einfache Hashtabelle, mit der zuvor berechnete Fibonacci-Zahlen wiederverwendet werden können, anstatt sie erneut auszuführen.

user3393266
quelle
1
import sys
sys.setrecursionlimit(1500)

def fib(n, sum):
    if n < 1:
        return sum
    else:
        return fib(n-1, sum+n)

c = 998
print(fib(c, 0))
user11462758
quelle
1
Dieselbe Antwort wurde schon oft gegeben. Bitte entfernen Sie es.
ZF007
0

Wir können das mit @lru_cacheDekorateur und setrecursionlimit()Methode tun :

import sys
from functools import lru_cache

sys.setrecursionlimit(15000)


@lru_cache(128)
def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fib(n - 2) + fib(n - 1)


print(fib(14000))

Ausgabe

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125

Quelle

functools lru_cache

Emma
quelle
0

Wir könnten auch eine Variation des Bottom-up-Ansatzes der dynamischen Programmierung verwenden

def fib_bottom_up(n):

    bottom_up = [None] * (n+1)
    bottom_up[0] = 1
    bottom_up[1] = 1

    for i in range(2, n+1):
        bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]

    return bottom_up[n]

print(fib_bottom_up(20000))
algowhiz
quelle