Какова максимальная глубина рекурсии в 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

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

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

Answer 2

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

sys.setrecursionlimit(1500)

Answer 3

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

с сайта python :

sys.getrecursionlimit()

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

Answer 7

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

Answer 8

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, ваша RAM исчерпает себя, что замедляет работу компьютера из-за безумия подкачки, или убивает Python с помощью OOM Killer.

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

ulimit -s
ulimit -s 10000

Значение по умолчанию для меня - 8 МБ.

См. также:

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

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

Answer 9

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

Answer 10

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

from numpy import matrix

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

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