Какова максимальная глубина рекурсии в Python и как ее увеличить?

Question

У меня есть эта хвостовая рекурсивная функция:

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

c = 998
print(fib(c, 0))

Работает до n = 997, затем просто ломается и выплевывает «максимальную глубину рекурсии, превышенную в сравнении» RuntimeError. Это просто переполнение стека? Есть ли способ обойти это?

Answer 1

Использовать генераторы?

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

над функцией fib (), адаптированной с: http://intermediatepythonista.com/python-generators

Answer 2

Многие рекомендуют, чтобы увеличение предела рекурсии было хорошим решением, однако это не так, потому что всегда будет ограничение.Вместо этого используйте итеративное решение.

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(5)

Answer 3

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

Answer 4

Я хотел бы дать вам пример использования мемоизации для вычисления Фибоначчи, поскольку это позволит вам вычислять значительно большие числа с использованием рекурсии:

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

Это все еще рекурсивно, но использует простую хеш-таблицу, которая позволяетповторное использование ранее вычисленных чисел Фибоначчи вместо их повторения.

Answer 5

Как @alex предложил , вы можете использовать функцию генератора для этого. Вот эквивалент кода в вашем вопросе:

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