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

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

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.

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

import sys
sys.setrecursionlimit(1500)

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().

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.

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

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

• Ustawienie stacksize w skrypcie python
• Jaki jest twardy limit rekurencji w systemach Linux, Mac i Windows?

Testowane na Ubuntu 16.10, Python 2.7.12.

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)

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.

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.

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.

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

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

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)

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.

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

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

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