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

Question

Ich habe diese Endrekursive 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 n=997, dann bricht es einfach ab und gibt einen RecursionError: maximum recursion depth exceeded in comparison aus. Ist das einfach ein Stacküberlauf? Gibt es einen Weg, das zu umgehen?

Answer 1

Es ist ein Schutz gegen einen Stack-Überlauf, ja. Python (bzw. die CPython-Implementierung) optimiert keine Endrekursion und ungebremste Rekursion führt zu Stack-Überläufen. Du kannst das Rekursionslimit mit sys.getrecursionlimit überprüfen:

import sys
print(sys.getrecursionlimit())

und das Rekursionslimit mit sys.setrecursionlimit ändern:

sys.setrecursionlimit(1500)

aber das ist gefährlich - das Standardlimit ist etwas konservativ, aber Python-Stackframes können ziemlich groß sein.

Python ist keine funktionale Sprache und Endrekursion ist keine besonders effiziente Technik. Das Algorithmus umzuschreiben, falls möglich, ist im Allgemeinen eine bessere Idee.

Answer 2

Es sieht so aus, als müssten Sie einfach eine höhere Rekursionstiefe festlegen:

import sys
sys.setrecursionlimit(1500)

Answer 3

Wenn Sie häufig den Rekursionslimit ändern müssen (z. B. beim Lösen von Programmieraufgaben), können Sie einen einfachen Kontext-Manager wie folgt definieren:

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)

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

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

Beim Verlassen des with-Blocks wird das Rekursionslimit auf den Standardwert zurückgesetzt.

P.S. Sie möchten vielleicht auch die Stackgröße des Python-Prozesses für hohe Werte des Rekursionslimits erhöhen. Das kann über das Shell-Builtin ulimit oder die Datei limits.conf(5) erfolgen, zum Beispiel.

Answer 4

Es dient zur Vermeidung eines Stapelüberlaufs. Der Python-Interpreter begrenzt die Rekursionstiefe, um zu verhindern, dass Sie unendliche Rekursionen erhalten, die zu Stapelüberläufen führen. Versuchen Sie, das Rekursionslimit zu erhöhen (sys.setrecursionlimit) 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-Stapels. Dieses Limit verhindert, dass unendliche Rekursionen einen Überlauf des C-Stapels verursachen und Python abstürzen lassen. Es kann durch setrecursionlimit() gesetzt werden.

Answer 5

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

Der Linux-Kernel beschränkt den Stapel von Prozessen.

Python speichert lokale Variablen auf dem Stapel des Interpreters, und so nimmt die Rekursion den Stapelspeicher des Interpreters ein.

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

Die Stapellimitgröße wird mit den Systemaufrufen getrlimit und setrlimit kontrolliert.

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

sys.setrecursionlimit erwähnt z.B. unter https://stackoverflow.com/a/3323013/895245 erhöht nur das Limit, das der Python-Interpreter selbst auf seine eigene Stapelgröße auferlegt, berührt aber nicht das Limit, das der Linux-Kernel dem Python-Prozess auferlegt.

Beispielsprogramm:

main.py

import resource
import sys

print resource.getrlimit(resource.RLIMIT_STACK)
print sys.getrecursionlimit()
print

# Würde ohne diese Zeile Segfault verursachen.
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 weiterhin setrlimit erhöhen, wird Ihr RAM irgendwann ausgehen, was entweder Ihren Computer aufgrund des Austausch-Irrsinns zum Stillstand bringen oder Python über den OOM-Killer beenden wird.

Von der Bash aus können Sie das Stapellimit (in kb) sehen und setzen mit:

ulimit -s
ulimit -s 10000

Der Standardwert für mich beträgt 8 MB.

Siehe auch:

• Das Stapelgrößenlimit in einem Python-Skript setzen
• Was ist das harte Rekursionslimit für Linux, Mac und Windows?

Getestet auf Ubuntu 16.10, Python 2.7.12.