Jaka jest maksymalna głębokość rekurencji w Pythonie i jak ją zwiększyć?

421

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ść?

quantumSoup
źródło
3
Zobacz także stackoverflow.com/questions/5061582/…
Thomas Ahle
9
zapamiętywanie może przyspieszyć twoją funkcję i zwiększyć jej efektywną głębokość rekurencyjną, powodując zakończenie wcześniej obliczonych wartości zamiast zwiększania wielkości stosu.
Cyoce,
2
Limit rekurencji wynosi zwykle 1000.
Boris
1
@tonix interpreter dodaje ramkę stosu ( line <n>, in <module>ślady w stosie), a ten kod przyjmuje 2 ramki stosu n=1(ponieważ tak jest ze względu na przypadek podstawowy n < 1, więc n=1wciąż 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 + 2jest mniejsza niż 1000, więc nie działa 998 + 2, ponieważ osiąga limit.
Boris,
1
@tonix no. recursive_function(997)działa, psuje się 998. Podczas wywołania recursive_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.
Boris,

Odpowiedzi:

469

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.getrecursionlimiti 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.

Thomas Wouters
źródło
4
Z mojego doświadczenia wynika, że ​​musisz zwiększyć limit zarówno w modułach, jak sysi w resource: stackoverflow.com/a/16248113/205521
Thomas Ahle
3
jako taktykę konwersji na wersję iteracyjną można zastosować dekorator optymalizacji wywołania ogona
jfs
3
możesz użyć svn.python.org/projects/python/trunk/Tools/scripts/…, aby sprawdzić górny limit systemu operacyjnego
Ullullu
8
Dla osób zainteresowanych źródłem domyślny limit rekurencji jest ustawiony na 1000 hg.python.org/cpython/file/tip/Python/ceval.c#l691 i można go zmienić za pomocą interfejsu API na hg.python.org/cpython /file/tip/Python/sysmodule.c#l643, który z kolei określa limit nowej wartości na hg.python.org/cpython/file/tip/Python/ceval.c#l703
Pramod
16
Rekurencja ogona jest doskonale wydajną techniką w zoptymalizowanym do tego języku programowania. W przypadku właściwego rodzaju problemu może być znacznie bardziej wyrazista i iteracyjna. Odpowiedź prawdopodobnie oznacza „konkretnie w Pythonie”, ale tak nie jest
Peter R,
135

Wygląda na to, że musisz tylko ustawić większą głębokość rekurencji :

import sys
sys.setrecursionlimit(1500)
David Young
źródło
W moim przypadku zapomniałem instrukcji return w przypadku podstawowym, która przekroczyła 1000. Python zaczął zgłaszać ten wyjątek i byłem zaskoczony, ponieważ byłem pewien, że nie. stosów, które zamierza stworzyć, aby go uruchomić.
vijayraj34
sys.setrecursionlimit (50) lub niewielka ilość jest przydatna, jeśli twój program wchodzi w cykl rekurencyjny i chciałbyś, aby komunikat o błędzie NIE JEST stronami i stronami tego samego tekstu. Uznałem to za bardzo pomocne podczas debugowania (mojego) złego kodu rekurencyjnego.
peawormsworth
56

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 :

sys.getrecursionlimit()

Zwraca bieżącą wartość limitu rekurencji, maksymalną głębokość stosu interpretera Pythona. Ten limit zapobiega nieskończonej rekurencji powodującej przepełnienie stosu C i zawieszenie Pythona. Można to ustawić za pomocą setrecursionlimit().

Scharron
źródło
W mojej Anaconda x64, 3.5 Python w systemie Windows domyślny limit to 1000.
Guillaume Chevalier
30

Jeśli często musisz zmienić limit rekurencji (np. Podczas rozwiązywania zagadek programistycznych), możesz zdefiniować prosty menedżer kontekstu, taki jak ten:

import sys

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

    def __enter__(self):
        sys.setrecursionlimit(self.limit)

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

Następnie, aby wywołać funkcję z niestandardowym limitem, możesz:

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

Po wyjściu z treści withinstrukcji limit rekurencji zostanie przywrócony do wartości domyślnej.

Eugene Yarmash
źródło
Chcesz również zwiększyć limit rekurencji procesuresource . Bez niego otrzymasz błąd segmentacji, a cały proces w języku Python ulegnie awarii, jeśli będziesz setrecursionlimitzbyt 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).
Boris
16

Użyj języka, który gwarantuje optymalizację połączeń ogonowych. Lub użyj iteracji. Alternatywnie, bądź słodki dzięki dekoratorom .

Marcelo Cantos
źródło
36
To raczej wylewanie dziecka z kąpielą.
Russell Borogove
3
@ Russell: Tylko jedna z oferowanych przeze mnie opcji doradza to.
Marcelo Cantos
„Bądź słodki z dekoratorami” nie jest opcją.
Pan B,
@ Mr.B, chyba że potrzebujesz więcej niż ulimit -sramek stosu, tak, to stackoverflow.com/a/50120316
Boris
14

resource.setrlimit należy również użyć, aby zwiększyć rozmiar stosu i zapobiec segfault

Ją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 getrlimiti setrlimit.

Python oferuje dostęp do tych wywołań systemowych za pośrednictwem resourcemodułu.

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)

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ą:

ulimit -s
ulimit -s 10000

Domyślna wartość to 8 Mb.

Zobacz też:

Testowane na Ubuntu 16.10, Python 2.7.12.

Ciro Santilli
źródło
1
Próba ustawienia rlimit_stackpo usunięciu konfliktu stosu może spowodować awarię lub powiązane problemy. Zobacz także Red Hat Issue 1463241
jww
Użyłem tego (część zasobów Python), aby pomóc w mojej implementacji algorytmu Kosaraju w średnim (ogromnym) zestawie danych profesora Tima Roughgarden. Moja implementacja działała na małych zestawach, z pewnością problemem z dużym zestawem danych był limit rekurencji / stosu ... A może tak? Cóż, tak było! Dzięki!
nilo
9

Zdaję 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:

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])

(Użyj n + 1 w xrange, jeśli zaczniesz liczyć sekwencję Fibonacciego od 0 zamiast 1)

Daniel
źródło
13
po co używać spacji O (n), skoro można korzystać z O (1)?
Janus Troelsen
11
Na wypadek gdyby komentarz do spacji O (n) był mylący: nie używaj listy. Lista zachowa wszystkie wartości, gdy wszystko czego potrzebujesz to n-ta wartość. Prostym algorytmem byłoby zachowanie dwóch ostatnich liczb Fibonacciego i dodawanie ich, aż dojdziesz do tej, której potrzebujesz. Są też lepsze algorytmy.
Milimetryczny
3
@Mathime: xrangenazywa się po prostu rangew Pythonie 3.
Eric O Lebigot
1
@EOL Zdaję sobie z tego sprawę
Mathime,
7
@Mathime Mówiłem wyraźnie o tych, którzy czytają te komentarze.
Eric O Lebigot,
9

Oczywiście liczby Fibonacciego można obliczyć w O (n), stosując wzór Bineta:

from math import floor, sqrt

def fib(n):                                                     
    return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5))

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ści Fibonacci(n)do tej wartości.

rwst
źródło
8
W pythonie nie ma maksymalnego rozmiaru długiego.
pppery
8
Warto zauważyć, że nie udaje się to w przypadku większej z npowodu niedokładności zmiennoprzecinkowej - różnica między (1+sqrt(5))**ni (1+sqrt(5))**(n+1)staje się mniejsza niż 1 ulp, więc zaczynasz uzyskiwać nieprawidłowe wyniki.
2
W NumPy nie ma tak naprawdę dużych liczb całkowitych…
Eric O Lebigot,
@Mego Co? Jest to różnica między (1+sqrt(5))**ni ((1+sqrt(5))**n)+1staje się mniejsza niż 1 ulp! (mała literówka) {@} rwst To nie jest O (1)! Obliczanie 2**nzajmuje co najmniej czas O (n).
user202729,
3
@ user202729 To nieprawda, obliczanie 2**njest efektywnie O (log (n)) przy użyciu wykładnika przez podniesienie do kwadratu .
Sam
6

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.

Tyler
źródło
2
OP podaje swój kod, a jego eksperyment jest powtarzalny do woli. Nie dotyczy uszkodzonych plików.
T. Verron
5
Masz rację, ale moja odpowiedź nie jest skierowana na OP, ponieważ było to ponad cztery lata temu. Moja odpowiedź ma na celu pomóc osobom z błędami MRD spowodowanymi pośrednio przez uszkodzone pliki - ponieważ jest to jeden z pierwszych wyników wyszukiwania. Pomogło komuś, skoro głosowano. Dziękuję za głosowanie w dół.
Tyler
2
To była jedyna rzecz, którą znalazłem gdziekolwiek, szukając mojego problemu, który połączył ślad „maksymalnej głębokości rekurencji” z uszkodzonym plikiem. Dzięki!
Jeff
5

Jeśli chcesz uzyskać tylko kilka liczb Fibonacciego, możesz użyć metody macierzowej.

from numpy import matrix

def fib(n):
    return (matrix('0 1; 1 1', dtype='object') ** n).item(1)

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.

bebidek
źródło
Niestety nie można używać numpy u większości konkurencyjnych sędziów programistycznych. Ale tak jest, moje rozwiązanie jest moim ulubionym. Użyłem rozwiązania macierzy do niektórych problemów. Jest to najlepsze rozwiązanie, gdy potrzebujesz bardzo dużej liczby Fibonacciego i nie możesz użyć modułu. Jeśli możesz użyć modułu, okres pisano jest lepszym sposobem, aby to zrobić.
mentatkgs
4

Używać generatorów?

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

fibs = fib() #seems to be the only way to get the following line to work is to
             #assign the infinite generator to a variable

f = [fibs.next() for x in xrange(1001)]

for num in f:
        print num

powyżej funkcji fib () zaadaptowanej z: http://intermediatepythonista.com/python-generators

alex
źródło
1
powodem przypisywania generatora do zmiennej jest [fibs().next() for ...]to, że za każdym razem tworzyłby nowy generator.
tox123
3

Jak sugerował @alex , możesz użyć funkcji generatora, aby zrobić to sekwencyjnie zamiast rekurencyjnie.

Oto odpowiednik kodu w twoim pytaniu:

def fib(n):
    def fibseq(n):
        """ Iteratively return the first n Fibonacci numbers, starting from 0. """
        a, b = 0, 1
        for _ in xrange(n):
            yield a
            a, b = b, a + b

    return sum(v for v in fibseq(n))

print format(fib(100000), ',d')  # -> no recursion depth error
martineau
źródło
2

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.

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(5)
Harun ERGUL
źródło
1

Chciałem dać ci przykład wykorzystania memoizacji do obliczenia Fibonacciego, ponieważ pozwoli ci to obliczyć znacznie większe liczby za pomocą rekurencji:

cache = {}
def fib_dp(n):
    if n in cache:
        return cache[n]
    if n == 0: return 0
    elif n == 1: return 1
    else:
        value = fib_dp(n-1) + fib_dp(n-2)
    cache[n] = value
    return value

print(fib_dp(998))

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.

użytkownik3393266
źródło
1
import sys
sys.setrecursionlimit(1500)

def fib(n, sum):
    if n < 1:
        return sum
    else:
        return fib(n-1, sum+n)

c = 998
print(fib(c, 0))
użytkownik 11462758
źródło
1
Ta sama odpowiedź została udzielona wiele razy. Proszę to usunąć.
ZF007
0

Możemy to zrobić za pomocą @lru_cachedekoratora i setrecursionlimit()metody:

import sys
from functools import lru_cache

sys.setrecursionlimit(15000)


@lru_cache(128)
def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fib(n - 2) + fib(n - 1)


print(fib(14000))

Wynik

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125

Źródło

funkools lru_cache

Emma
źródło
0

Moglibyśmy również zastosować odmianę podejścia do programowania dynamicznego oddolnego

def fib_bottom_up(n):

    bottom_up = [None] * (n+1)
    bottom_up[0] = 1
    bottom_up[1] = 1

    for i in range(2, n+1):
        bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]

    return bottom_up[n]

print(fib_bottom_up(20000))
algowhiz
źródło