In Python gibt es eine Obergrenze für die Anzahl der Rekursionen (die maximale Anzahl von Rekursionen). Um eine rekursive Funktion mit einer großen Anzahl von Aufrufen auszuführen, ist es notwendig, diese Grenze zu ändern. Verwenden Sie die Funktionen im Modul sys der Standardbibliothek.
Die Anzahl der Rekursionen wird auch durch die Stack-Größe begrenzt. In einigen Umgebungen kann das Ressourcenmodul der Standardbibliothek verwendet werden, um die maximale Stackgröße zu ändern (unter Ubuntu funktionierte es, aber nicht unter Windows oder Mac).
Hier finden Sie die folgenden Informationen.
- Ermittelt die Obergrenze der aktuellen Anzahl von Rekursionen:
sys.getrecursionlimit() - Ändern Sie die Obergrenze für die Anzahl der Rekursionen:
sys.setrecursionlimit() - Ändern Sie die maximale Größe des Stapels:
resource.setrlimit()
Der Beispielcode läuft auf Ubuntu.
Ermitteln der aktuellen Rekursionsgrenze: sys.getrecursionlimit()
Die aktuelle Rekursionsgrenze kann mit sys.getrecursionlimit() ermittelt werden.
import sys
import resource
print(sys.getrecursionlimit())
# 1000
In diesem Beispiel beträgt die maximale Anzahl der Rekursionen 1000, was je nach Umgebung variieren kann. Beachten Sie, dass die Ressource, die wir hier importieren, später verwendet wird, aber nicht unter Windows.
Als Beispiel soll die folgende einfache rekursive Funktion dienen. Wenn eine positive ganze Zahl n als Argument angegeben wird, wird die Funktion n-mal aufgerufen.
def recu_test(n):
if n == 1:
print('Finish')
return
recu_test(n - 1)
Ein Fehler (RecursionError) wird ausgelöst, wenn Sie versuchen, eine Rekursion über die Obergrenze hinaus durchzuführen.
recu_test(950)
# Finish
# recu_test(1500)
# RecursionError: maximum recursion depth exceeded in comparison
Beachten Sie, dass der von sys.getrecursionlimit() ermittelte Wert nicht unbedingt die maximale Anzahl der Rekursionen ist, sondern die maximale Stapeltiefe des Python-Interpreters, so dass selbst bei einer geringfügig geringeren Anzahl von Rekursionen als diesem Wert ein Fehler (RecursionError) ausgelöst wird.
Die Rekursionsgrenze ist nicht die Grenze der Rekursion, sondern die maximale Tiefe des Stacks des Python-Interpreters.
python – Max recursion is not exactly what sys.getrecursionlimit() claims. How come? – Stack Overflow
# recu_test(995)
# RecursionError: maximum recursion depth exceeded while calling a Python object
Rekursionsgrenze ändern: sys.setrecursionlimit()
Die Obergrenze für die Anzahl der Rekursionen kann mit sys.setrecursionlimit() geändert werden. Die Obergrenze wird als Argument angegeben.
Ermöglicht die Durchführung einer tieferen Rekursion.
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())
# 2000
recu_test(1500)
# Finish
Wenn die angegebene Obergrenze zu klein oder zu groß ist, tritt ein Fehler auf. Diese Einschränkung (Ober- und Untergrenze des Limits selbst) variiert je nach Umgebung.
Der maximale Wert von limit hängt von der Plattform ab. Wenn Sie eine tiefe Rekursion benötigen, können Sie einen größeren Wert innerhalb des von der Plattform unterstützten Bereichs angeben, aber beachten Sie, dass dieser Wert zu einem Absturz führt, wenn er zu groß ist.
If the new limit is too low at the current recursion depth, a RecursionError exception is raised.
sys.setrecursionlimit() — System-specific parameters and functions — Python 3.10.0 Documentation
sys.setrecursionlimit(4)
print(sys.getrecursionlimit())
# 4
# sys.setrecursionlimit(3)
# RecursionError: cannot set the recursion limit to 3 at the recursion depth 1: the limit is too low
sys.setrecursionlimit(10 ** 9)
print(sys.getrecursionlimit())
# 1000000000
# sys.setrecursionlimit(10 ** 10)
# OverflowError: signed integer is greater than maximum
Die maximale Anzahl der Rekursionen wird auch durch die Stack-Größe begrenzt, wie im Folgenden erklärt wird.
Ändern Sie die maximale Größe des Stapels: resource.setrlimit()
Selbst wenn in sys.setrecursionlimit() ein großer Wert eingestellt wird, kann er nicht ausgeführt werden, wenn die Anzahl der Rekursionen groß ist. Ein Segmentierungsfehler tritt wie folgt auf.
sys.setrecursionlimit(10 ** 9)
print(sys.getrecursionlimit())
# 1000000000
recu_test(10 ** 4)
# Finish
# recu_test(10 ** 5)
# Segmentation fault
In Python kann das Ressourcenmodul in der Standardbibliothek verwendet werden, um die maximale Stapelgröße zu ändern. Das Ressourcenmodul ist jedoch ein Unix-spezifisches Modul und kann unter Windows nicht verwendet werden.
- Unix Specific Services — Python 3.10.0 Documentation
- resource — Resource usage information — Python 3.10.0 Documentation
Mit resource.getrlimit() können Sie das Limit der im Argument angegebenen Ressource als Tupel von (soft limit, hard limit) abrufen. Hier geben wir resource.RLIMIT_STACK als Ressource an, die die maximale Größe des Aufrufstapels des aktuellen Prozesses darstellt.
- resource.getrlimit() — Resource usage information — Python 3.10.0 Documentation
- resource.RLIMIT_STACK — Resource usage information — Python 3.10.0 Documentation
print(resource.getrlimit(resource.RLIMIT_STACK))
# (8388608, -1)
In diesem Beispiel beträgt die weiche Grenze 8388608 (8388608 B = 8192 KB = 8 MB) und die harte Grenze -1 (unbegrenzt).
Sie können das Limit der Ressource mit resource.setrlimit() ändern. Auch hier wird das weiche Limit auf -1 (kein Limit) gesetzt. Sie können auch die Konstante resource.RLIM_INFINIT verwenden, um das unbegrenzte Limit darzustellen.
Die tiefe Rekursion, die vor der Änderung der Stackgröße aufgrund eines Segmentierungsfehlers nicht durchgeführt werden konnte, kann nun durchgeführt werden.
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))
print(resource.getrlimit(resource.RLIMIT_STACK))
# (-1, -1)
recu_test(10 ** 5)
# Finish
Hier ist die weiche Grenze für ein einfaches Experiment auf -1 (keine Grenze) gesetzt, aber in der Realität wäre es sicherer, sie auf einen geeigneten Wert zu begrenzen.
Als ich außerdem versuchte, auch auf meinem Mac ein unbegrenztes Softlimit festzulegen, trat folgender Fehler auf.ValueError: not allowed to raise maximum limit
Das Ausführen des Skripts mit sudo hat nicht geholfen. Möglicherweise ist es durch das System eingeschränkt.
Ein Prozess mit der effektiven UID eines Superusers kann jede vernünftige Begrenzung anfordern, einschließlich keiner Begrenzung.
Eine Anfrage, die die vom System festgelegte Grenze überschreitet, führt jedoch zu einem ValueError.
resource.setrlimit() — Resource usage information — Python 3.10.0 Documentation
Windows verfügt nicht über ein Ressourcenmodul, und mac konnte die maximale Stackgröße aufgrund von Systembeschränkungen nicht ändern. Wenn wir die Stack-Größe auf irgendeine Weise erhöhen können, sollten wir in der Lage sein, den Segmentierungsfehler zu lösen, aber wir waren nicht in der Lage, dies zu bestätigen.
