wake-up-neo.com

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

Ich habe diese rekursive Schwanzfunktion 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 nur und spuckt eine "maximale Rekursionstiefe, die im Vergleich überschritten wurde" RuntimeError. Ist das nur ein Stapelüberlauf? Gibt es einen Weg, um es zu umgehen?

314
quantumSoup

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 sys.getrecursionlimit überprüfen und das Rekursionslimit mit sys.setrecursionlimit ändern, dies ist jedoch gefährlich - das Standardlimit ist a wenig konservativ, aber Python Stackframes können ziemlich groß sein.

Python ist keine funktionale Sprache und die Schwanzrekursion ist keine besonders effiziente Technik. Im Allgemeinen ist es besser, den Algorithmus nach Möglichkeit iterativ umzuschreiben.

359
Thomas Wouters

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

sys.setrecursionlimit(1500)
102
David Young

Es geht darum, einen Stapelüberlauf zu vermeiden. Der Python -Interpreter begrenzt die Tiefe der Rekursion, um unendliche Rekursionen zu vermeiden, die zu Stapelüberläufen führen. Erhöhen Sie das Rekursionslimit (sys.setrecursionlimit) oder schreiben Sie Ihren Code ohne Rekursion neu.

from Python-Website :

sys.getrecursionlimit()

Liefert den aktuellen Wert des Rekursionslimits, die maximale Tiefe des Python Interpreter-Stacks. Diese Grenze verhindert, dass eine unendliche Rekursion zu einem Überlauf des C-Stacks und zum Absturz von Python führt. Es kann mit setrecursionlimit () gesetzt werden.

46
Scharron

Verwenden Sie eine Sprache, die eine Tail-Call-Optimierung garantiert. Oder benutze Iteration. Alternativ kannst du auch Dekorateure verwenden.

17
Marcelo Cantos

Wenn Sie häufig das Rekursionslimit ändern müssen (z. B. beim Lösen von Programmierpuzzles), können Sie ein einfaches 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)

Dann können Sie eine Funktion mit einem benutzerdefinierten Limit aufrufen:

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

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

14
Eugene Yarmash

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

10
Daniel

Natürlich können Fibonacci-Zahlen in O(n) berechnet werden, indem die Binet-Formel angewendet wird:

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 weiterer Unterschied ist, dass Sie nur einen Wert erhalten, während Sie mit der Rekursion alle Werte von Fibonacci(n) bis zu diesem Wert erhalten.

9
rwst

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 im Stapel des Interpreters, sodass die Rekursion den Stapelspeicher des Interpreters beansprucht.

Wenn der Python -Interpreter versucht, das Stack-Limit zu überschreiten, führt der Linux-Kernel einen Segmentierungsfehler aus.

Die Stack-Limit-Größe wird mit den Systemaufrufen getrlimit und setrlimit gesteuert.

Python bietet Zugriff auf diese Systemaufrufe über das Modul 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 Sie das ulimit erhöhen, wird Ihr RAM ausgehen, was entweder Ihren Computer aufgrund von Tauschwahnsinn zum Stillstand bringt oder Python über den OOM Killer tötet.

In bash können Sie das Stack-Limit (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.

Ich hatte ein ähnliches Problem mit dem Fehler "Maximale Rekursionstiefe überschritten". Ich entdeckte, dass der Fehler durch eine beschädigte Datei in dem Verzeichnis ausgelöst wurde, über das ich mit os.walk eine Schleife durchführte. Wenn Sie Probleme bei der Behebung dieses Problems haben und mit Dateipfaden arbeiten, sollten Sie diesen einschränken, da es sich möglicherweise um eine beschädigte Datei handelt.

6
Tyler

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

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

4
alex

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 so schnell, wie Numpy den schnellen Exponentiationsalgorithmus verwendet. Sie erhalten eine Antwort in O (log n). Und es ist besser als die Formel von Binet, weil es nur Ganzzahlen verwendet. Aber wenn Sie alle Fibonacci-Zahlen bis n wollen, ist es besser, dies durch Auswendiglernen zu tun.

4
bebidek

Viele empfehlen, das Rekursionslimit zu erhöhen, was jedoch nicht der Fall ist, da 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)
2
Harun ERGUL

Ich wollte Ihnen ein Beispiel für die Verwendung von Memoization 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 Hash-Tabelle, mit der zuvor berechnete Fibonacci-Zahlen wiederverwendet werden können, anstatt sie erneut auszuführen.

1
user3393266

Als @alex vorgeschlagen könnten Sie eine Generatorfunktion verwenden, um dies zu tun. 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
1
martineau
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))
1
user11462758