V jazyce Python existuje horní hranice počtu rekurzí (maximální počet rekurzí). Chcete-li provést rekurzivní funkci s velkým počtem volání, je nutné tento limit změnit. Použijte funkce v modulu sys standardní knihovny.
Počet rekurzí je rovněž omezen velikostí zásobníku. V některých prostředích lze pomocí modulu resource standardní knihovny změnit maximální velikost zásobníku (fungovalo to v Ubuntu, ale ne ve Windows nebo Macu).
Zde jsou uvedeny následující informace.
- Zjištění horní hranice aktuálního počtu rekurzí:
sys.getrecursionlimit() - Změna horní hranice počtu rekurzí:
sys.setrecursionlimit() - Změna maximální velikosti zásobníku:
resource.setrlimit()
Ukázkový kód je spuštěn v systému Ubuntu.
Zjištění aktuálního limitu rekurze: sys.getrecursionlimit()
Aktuální limit rekurze lze zjistit pomocí sys.getrecursionlimit().
import sys
import resource
print(sys.getrecursionlimit())
# 1000
V příkladu je maximální počet rekurzí 1000, což se může lišit v závislosti na prostředí. Všimněte si, že prostředek, který zde importujeme, bude použit později, ale ne v systému Windows.
Jako příklad použijeme následující jednoduchou rekurzivní funkci. Pokud je jako argument zadáno celé kladné číslo n, bude počet volání n-násobný.
def recu_test(n):
if n == 1:
print('Finish')
return
recu_test(n - 1)
Pokud se pokusíte provést více rekurzí, než je horní mez, bude vyvolána chyba (RecursionError).
recu_test(950)
# Finish
# recu_test(1500)
# RecursionError: maximum recursion depth exceeded in comparison
Všimněte si, že hodnota získaná pomocí sys.getrecursionlimit() není striktně maximální počet rekurzí, ale maximální hloubka zásobníku interpretu jazyka Python, takže i když je počet rekurzí o něco menší než tato hodnota, bude vyvolána chyba (RecursionError).
Limit rekurze není limit rekurze, ale maximální hloubka zásobníku interpretu jazyka python.
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
Změna limitu rekurze: sys.setrecursionlimit()
Horní hranici počtu rekurzí lze změnit pomocí funkce sys.setrecursionlimit(). Horní limit se zadává jako argument.
Umožňuje provádět hlubší rekurzi.
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())
# 2000
recu_test(1500)
# Finish
Pokud je zadaná horní mez příliš malá nebo příliš velká, dojde k chybě. Toto omezení (horní a dolní hranice samotného limitu) se mění v závislosti na prostředí.
Maximální hodnota limitu závisí na platformě. Pokud potřebujete hlubokou rekurzi, můžete zadat větší hodnotu v rámci rozsahu podporovaného platformou, ale uvědomte si, že tato hodnota způsobí pád, pokud je příliš velká.
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
Maximální počet rekurzí je také omezen velikostí zásobníku, jak je vysvětleno dále.
Změna maximální velikosti zásobníku: resource.setrlimit()
I když je v příkazu sys.setrecursionlimit() nastavena velká hodnota, nemusí být příkaz proveden, pokud je počet rekurzí velký. K segmentační chybě dojde následujícím způsobem.
sys.setrecursionlimit(10 ** 9)
print(sys.getrecursionlimit())
# 1000000000
recu_test(10 ** 4)
# Finish
# recu_test(10 ** 5)
# Segmentation fault
V jazyce Python lze ke změně maximální velikosti zásobníku použít modul resource ve standardní knihovně. Modul resource je však specifický pro Unix a nelze jej použít v systému Windows.
- Unix Specific Services — Python 3.10.0 Documentation
- resource — Resource usage information — Python 3.10.0 Documentation
Pomocí funkce resource.getrlimit() můžete získat limit prostředku zadaný v argumentu jako tuple (soft limit, hard limit). Zde zadáváme resource.RLIMIT_STACK jako prostředek, který představuje maximální velikost zásobníku volání aktuálního procesu.
- 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)
V příkladu je měkký limit 8388608 (8388608 B = 8192 KB = 8 MB) a tvrdý limit je -1 (neomezený).
Limit prostředku můžete změnit pomocí resource.setrlimit(). Zde je měkký limit také nastaven na -1 (bez limitu). Můžete také použít konstantu resource.RLIM_INFINIT, která představuje neomezený limit.
Hlubokou rekurzi, kterou před změnou velikosti zásobníku nebylo možné provést kvůli chybě segmentace, lze nyní provést.
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))
print(resource.getrlimit(resource.RLIMIT_STACK))
# (-1, -1)
recu_test(10 ** 5)
# Finish
Zde je měkký limit nastaven na -1 (žádný limit) pro jednoduchý experiment, ale ve skutečnosti by bylo bezpečnější jej omezit na vhodnou hodnotu.
Když jsem se navíc pokusil nastavit neomezený softwarový limit i na svém macu, objevila se následující chyba.ValueError: not allowed to raise maximum limit
Spuštění skriptu se sudo nepomohlo. Může to být omezeno systémem.
Proces s efektivním UID superuživatele může požadovat jakýkoli rozumný limit, včetně žádného limitu.
Požadavek, který překročí limit stanovený systémem, však stále vede k chybě ValueError.
resource.setrlimit() — Resource usage information — Python 3.10.0 Documentation
Systém Windows nemá modul prostředků a systém Mac nemohl změnit maximální velikost zásobníku kvůli systémovým omezením. Pokud se nám podaří nějakým způsobem zvětšit velikost zásobníku, měli bychom být schopni vyřešit chybu segmentace, ale nepodařilo se nám to potvrdit.
