Почему существует RecursionError [duplicate]

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

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

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

from numpy import matrix

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

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

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

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

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

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

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

Если интерпретатор Python пытается преодолеть ограничение стека, ядро ​​Linux segfaults.

Размер ограничения стека равен управляется системными вызовами 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 Killer.

Из bash вы можете увидеть и установить ограничение стека ( в kb) с:

ulimit -s
ulimit -s 10000

Значение по умолчанию для меня равно 8Mb.

См. также:

• Настройка стекирования в питоне script
• Python: Каков предел жесткой рекурсии для Linux, Mac и Windows?

Проверено на Ubuntu 16.10, Python 2.7.12.

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

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

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

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

sys.setrecursionlimit(1500)

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

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 предел рекурсии будет восстановлен до значения по умолчанию.

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

Конечно, числа Фибоначчи могут быть вычислены в 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) до этого значения.

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

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

из веб-сайта python :

sys.getrecursionlimit()

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