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

Question 1

Ich habe diese tail rekursive Funktion 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 zu n=997dann bricht es einfach ab und spuckt einen aus RecursionError: maximum recursion depth exceeded in comparison. Ist das nur ein Stapelüberlauf? Gibt es eine Möglichkeit, es zu umgehen?

Question 2

Es ist ein Schutz gegen einen Stapelüberlauf, ja. Python (oder besser gesagt die CPython-Implementierung) optimiert die Schwanzrekursion nicht, und ungezügelte Rekursion verursacht Stapelüberläufe. Sie können das Rekursionslimit mit überprüfen sys.getrecursionlimit:

import sys
print(sys.getrecursionlimit())

und ändern Sie die Rekursionsgrenze mit sys.setrecursionlimit:

sys.setrecursionlimit(1500)

Dies ist jedoch gefährlich – die Standardgrenze ist ein wenig konservativ, aber Python-Stackframes können ziemlich groß sein.

Python ist keine funktionale Sprache und Schwanzrekursion ist keine besonders effiziente Technik. Wenn möglich, ist es im Allgemeinen eine bessere Idee, den Algorithmus iterativ neu zu schreiben.

Question 3

Sieht so aus, als müsstest du es einfach tun Stellen Sie eine höhere Rekursionstiefe ein:

import sys
sys.setrecursionlimit(1500)

Question 4

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

Von dem Python-Dokumentation:

sys.getrecursionlimit()

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

Question 5

Wenn Sie die Rekursionsgrenze oft ändern müssen (z. B. beim Lösen von Programmierrätseln), können Sie eine einfache definieren Kontextmanager so was:

import sys

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

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

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

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

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

Beim Austritt aus dem Körper der with -Anweisung wird das Rekursionslimit auf den Standardwert zurückgesetzt.

PS Möglicherweise möchten Sie auch die Stapelgröße des Python-Prozesses für große Werte des Rekursionslimits erhöhen. Das geht über die ulimit Shell eingebaut oder limits.conf(5) Datei zum Beispiel.

Question 6

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 Stack des Interpreters, sodass die Rekursion Stack-Speicherplatz des Interpreters beansprucht.

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

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

Python bietet Zugriff auf diese Systemaufrufe über die resource Modul.

sys.setrecursionlimit B. unter https://stackoverflow.com/a/3323013/895245 erwähnt, erhöht nur die Grenze, die der Python-Interpreter selbst seiner eigenen Stapelgröße auferlegt, berührt aber nicht die Grenze, die der Linux-Kernel dem Python-Prozess auferlegt.

Beispielprogramm:

main.py

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 weiter zunehmen setrlimitwird Ihr RAM irgendwann knapp, was entweder Ihren Computer aufgrund von Swap-Wahnsinn zum Stillstand bringt oder Python über den OOM Killer tötet.

Von bash aus können Sie das Stack-Limit (in kb) sehen und festlegen mit:

ulimit -s
ulimit -s 10000

Der Standardwert für mich ist 8 MB.

Siehe auch:

Stapelgröße in einem Python-Skript festlegen
Was ist das Hard-Recursion-Limit für Linux, Mac und Windows?

Getestet auf Ubuntu 16.10, Python 2.7.12.

Question 7

Verwenden Sie eine Sprache, die Tail-Call-Optimierung garantiert. Oder verwenden Sie die Iteration. Alternativ werden Sie süß mit Dekorateure.

Question 8

Mir ist klar, dass dies eine alte Frage ist, aber für diejenigen, die lesen, würde ich davon abraten, Rekursion für Probleme wie diese zu verwenden – Listen sind viel schneller und vermeiden Rekursion vollständig. Ich würde dies wie folgt implementieren:

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-Folge bei 0 statt bei 1 zu zählen.)