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

Похоже, вам просто нужно установить более высокую глубину рекурсии

sys.setrecursionlimit(1500)

чтобы избежать переполнения стека. Интерпретатор Python ограничивает глубину рекурсии, чтобы помочь вам избежать бесконечных рекурсий, что приводит к переполнению стека. Попробуйте увеличить предел рекурсии (sys.setrecursionlimit) или переписывание кода без рекурсии.

С сайт python:

sys.getrecursionlimit()

возвращает текущее значение предела рекурсии, максимальную глубину стека интерпретатора Python. Это ограничение предотвращает бесконечная рекурсия из-за переполнения стека C и сбоя Python. Он может быть установлен с помощью setrecursionlimit ().

используйте язык, который гарантирует оптимизацию хвостового вызова. Или использовать итерации. Кроме того, получить мило с декораторы.

Я понимаю, что это старый вопрос, но для тех, кто читает, я бы рекомендовал не использовать рекурсию для таких проблем, как это - списки намного быстрее и полностью избегают рекурсии. Я бы реализовал это как:

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

(используйте n+1 в xrange, если вы начинаете считать свою последовательность Фибоначчи от 0 вместо 1.)

конечно, числа Фибоначчи могут быть вычислены в O( n), применяя формулу Бине:

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

как отмечают комментаторы, это не O (1), а O(n) из-за 2**n. Также разница в том, что вы получаете только одно значение, в то время как с рекурсией вы получаете все значения Fibonacci(n) до этого значения.

У меня была аналогичная проблема с ошибкой "максимальная глубина рекурсии превысил". Я обнаружил, что ошибка была вызвана поврежденным файлом в каталоге, который я перебирал с ОС.ходить. Если у вас возникли проблемы с решением этой проблемы, и вы работаете с путями к файлам, не забудьте сузить его, так как это может быть поврежденный файл.

resource.setrlimit также необходимо использовать для увеличения размера стека и предотвращения segfault

ядро Linux ограничивает стек процессов.

Python хранит локальные переменные в стеке интерпретатора, и поэтому рекурсия занимает пространство стека интерпретатора.

если интерпретатор Python пытается перейти предел стека, ядро Linux сегментирует его.

размер предела стека управляется с помощью getrlimit и setrlimit системный вызов.

Python предлагает доступ к этим системным вызовам через resource модуль.

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)

конечно, если вы продолжаете увеличивать ulimit, ваша оперативная память закончится, что либо замедлит ваш компьютер до остановки из-за безумия свопа, либо убьет Python через убийцу OOM.

от bash, вы можете увидеть и установить предел стека (в КБ) с:

ulimit -s
ulimit -s 10000

значение по умолчанию для меня составляет 8 МБ.

посмотреть также:

• установка размера стека в скрипте python
• Python: что такое жесткий предел рекурсии для Linux, Mac и Windows?

протестировано на Ubuntu 16.10, Python 2.7.12.

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

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

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

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

Если вы хотите получить только несколько чисел Фибоначчи, можно использовать матричный метод.

from numpy import matrix

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

это быстро, как numpy использует быстрый алгоритм возведения в степень. Вы получаете ответ в O (log n). И это лучше, чем формула Бине, потому что она использует только целые числа. Но если вы хотите, чтобы все числа Фибоначчи до n, то лучше сделать это запоминание.

Если вам часто нужно изменить предел рекурсии (например, при решении головоломок программирования), вы можете определить простой контекст менеджер такой:

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)

затем для вызова функции с пользовательским ограничением вы можете сделать:

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

на выходе из тела with оператор предел рекурсии будет восстановлен до значения по умолчанию.

как @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