Mam tutaj tę funkcję rekurencyjną:
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))
Działa to n=997
, a potem po prostu pęka i wypluwa RecursionError: maximum recursion depth exceeded in comparison
. Czy to tylko przepełnienie stosu? Czy można to obejść?
line <n>, in <module>
ślady w stosie), a ten kod przyjmuje 2 ramki stosun=1
(ponieważ tak jest ze względu na przypadek podstawowyn < 1
, więcn=1
wciąż się powtarza). I myślę, że limit rekurencji nie jest wliczony, ponieważ jest to „błąd, gdy trafisz 1000”, „nie” błąd, jeśli przekroczysz 1000 (1001) ”.997 + 2
jest mniejsza niż 1000, więc nie działa998 + 2
, ponieważ osiąga limit.recursive_function(997)
działa, psuje się998
. Podczas wywołaniarecursive_function(998)
używa 999 ramek stosu, a interpreter dodaje 1 ramkę (ponieważ kod jest zawsze uruchamiany tak, jakby był częścią modułu najwyższego poziomu), co powoduje, że osiąga limit 1000.Odpowiedzi:
Jest to ochrona przed przepełnieniem stosu, tak. Python (a raczej implementacja CPython) nie optymalizuje rekurencji ogona, a nieokreślona rekurencja powoduje przepełnienie stosu. Możesz sprawdzić limit rekurencji za pomocą
sys.getrecursionlimit
i zmienić limit rekurencji za pomocąsys.setrecursionlimit
, ale jest to niebezpieczne - standardowy limit jest nieco konserwatywny, ale ramki stosu Pythona mogą być dość duże.Python nie jest językiem funkcjonalnym, a rekurencja ogona nie jest szczególnie skuteczną techniką. Iteracyjne przepisywanie algorytmu, jeśli to możliwe, jest ogólnie lepszym pomysłem.
źródło
sys
i wresource
: stackoverflow.com/a/16248113/205521Wygląda na to, że musisz tylko ustawić większą głębokość rekurencji :
źródło
Ma to na celu uniknięcie przepełnienia stosu. Interpreter języka Python ogranicza głębokość rekurencji, aby pomóc uniknąć nieskończonych rekurencji, co powoduje przepełnienie stosu. Spróbuj zwiększyć limit rekurencji (
sys.setrecursionlimit
) lub ponownie napisać kod bez rekurencji.Z dokumentacji Python :
źródło
Jeśli często musisz zmienić limit rekurencji (np. Podczas rozwiązywania zagadek programistycznych), możesz zdefiniować prosty menedżer kontekstu, taki jak ten:
Następnie, aby wywołać funkcję z niestandardowym limitem, możesz:
Po wyjściu z treści
with
instrukcji limit rekurencji zostanie przywrócony do wartości domyślnej.źródło
resource
. Bez niego otrzymasz błąd segmentacji, a cały proces w języku Python ulegnie awarii, jeśli będzieszsetrecursionlimit
zbyt wysoko i spróbujesz użyć nowego limitu (około 8 megabajtów ramek stosu, co przekłada się na ~ 30 000 ramek stosu z prostą funkcją powyżej, na mój laptop).Użyj języka, który gwarantuje optymalizację połączeń ogonowych. Lub użyj iteracji. Alternatywnie, bądź słodki dzięki dekoratorom .
źródło
ulimit -s
ramek stosu, tak, to stackoverflow.com/a/50120316resource.setrlimit
należy również użyć, aby zwiększyć rozmiar stosu i zapobiec segfaultJądro Linux ogranicza stos procesów .
Python przechowuje zmienne lokalne na stosie interpretera, a zatem rekurencja zajmuje przestrzeń stosu interpretera.
Jeśli interpreter Pythona próbuje przekroczyć limit stosu, jądro Linuksa powoduje błąd segmentacji.
Rozmiar limitu stosu jest kontrolowany za pomocą wywołań systemowych
getrlimit
isetrlimit
.Python oferuje dostęp do tych wywołań systemowych za pośrednictwem
resource
modułu.Oczywiście, jeśli nadal będziesz zwiększać ulimit, skończy się pamięć RAM, co albo spowolni twój komputer z powodu zamiany szaleństwa, albo zabije Pythona za pomocą OOM Killera.
Z basha możesz zobaczyć i ustawić limit stosu (w KB) za pomocą:
Domyślna wartość to 8 Mb.
Zobacz też:
Testowane na Ubuntu 16.10, Python 2.7.12.
źródło
rlimit_stack
po usunięciu konfliktu stosu może spowodować awarię lub powiązane problemy. Zobacz także Red Hat Issue 1463241Zdaję sobie sprawę, że to stare pytanie, ale dla osób czytających odradzam używanie rekurencji w przypadku takich problemów - listy są znacznie szybsze i całkowicie unikają rekurencji. Zaimplementowałbym to jako:
(Użyj n + 1 w xrange, jeśli zaczniesz liczyć sekwencję Fibonacciego od 0 zamiast 1)
źródło
xrange
nazywa się po prosturange
w Pythonie 3.Oczywiście liczby Fibonacciego można obliczyć w O (n), stosując wzór Bineta:
Jak zauważają komentatorzy, nie jest to O (1), ale O (n) z powodu
2**n
. Różnica polega także na tym, że otrzymujesz tylko jedną wartość, podczas gdy z rekurencją otrzymujesz wszystkie wartościFibonacci(n)
do tej wartości.źródło
n
powodu niedokładności zmiennoprzecinkowej - różnica między(1+sqrt(5))**n
i(1+sqrt(5))**(n+1)
staje się mniejsza niż 1 ulp, więc zaczynasz uzyskiwać nieprawidłowe wyniki.(1+sqrt(5))**n
i((1+sqrt(5))**n)+1
staje się mniejsza niż 1 ulp! (mała literówka) {@} rwst To nie jest O (1)! Obliczanie2**n
zajmuje co najmniej czas O (n).2**n
jest efektywnie O (log (n)) przy użyciu wykładnika przez podniesienie do kwadratu .Miałem podobny problem z błędem „Przekroczono maksymalną głębokość rekurencji”. Odkryłem, że błąd był wywoływany przez uszkodzony plik w katalogu, z którym się zapętlałem
os.walk
. Jeśli masz problemy z rozwiązaniem tego problemu i pracujesz ze ścieżkami do plików, zawęż je, ponieważ może to być uszkodzony plik.źródło
Jeśli chcesz uzyskać tylko kilka liczb Fibonacciego, możesz użyć metody macierzowej.
Jest szybki, ponieważ numpy używa algorytmu szybkiego potęgowania. Odpowiedź otrzymasz w O (log n). Jest to lepsze niż formuła Bineta, ponieważ używa tylko liczb całkowitych. Ale jeśli chcesz mieć wszystkie liczby Fibonacciego do n, lepiej zrobić to przez zapamiętywanie.
źródło
Używać generatorów?
powyżej funkcji fib () zaadaptowanej z: http://intermediatepythonista.com/python-generators
źródło
[fibs().next() for ...]
to, że za każdym razem tworzyłby nowy generator.Jak sugerował @alex , możesz użyć funkcji generatora, aby zrobić to sekwencyjnie zamiast rekurencyjnie.
Oto odpowiednik kodu w twoim pytaniu:
źródło
Wielu zaleca, aby zwiększenie limitu rekurencji było dobrym rozwiązaniem, jednak nie dlatego, że zawsze będzie limit. Zamiast tego użyj iteracyjnego rozwiązania.
źródło
Chciałem dać ci przykład wykorzystania memoizacji do obliczenia Fibonacciego, ponieważ pozwoli ci to obliczyć znacznie większe liczby za pomocą rekurencji:
Jest to wciąż rekurencyjne, ale używa prostego hashtable, który pozwala na ponowne użycie wcześniej obliczonych liczb Fibonacciego zamiast robić to ponownie.
źródło
źródło
Możemy to zrobić za pomocą
@lru_cache
dekoratora isetrecursionlimit()
metody:Wynik
Źródło
funkools lru_cache
źródło
Moglibyśmy również zastosować odmianę podejścia do programowania dynamicznego oddolnego
źródło