Какова максимальная глубина рекурсии в Python и как ее увеличить?
У меня есть эта хвостовая рекурсивная функция здесь:
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, Это просто переполнение стека? Есть ли способ обойти это?
19 ответов
Да, это защита от переполнения стека. Python (точнее, реализация CPython) не оптимизирует хвостовую рекурсию, а необузданная рекурсия вызывает переполнение стека. Вы можете изменить лимит рекурсии с sys.setrecursionlimit, но делать это опасно - стандартное ограничение немного консервативно, но стековые рамки Python могут быть довольно большими.
Python не является функциональным языком, а хвостовая рекурсия не особенно эффективна. Переписывание алгоритма итеративно, если это возможно, обычно является лучшей идеей.
Похоже, вам просто нужно установить более высокую глубину рекурсии
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 В заявлении предел рекурсии будет восстановлен до значения по умолчанию.
Это чтобы избежать переполнения стека. Интерпретатор Python ограничивает глубину рекурсии, чтобы помочь вам избежать бесконечных рекурсий, что приводит к переполнению стека. Попробуйте увеличить предел рекурсии (sys.setrecursionlimit) или переписать свой код без рекурсии.
с сайта Python:
sys.getrecursionlimit()Возвращает текущее значение предела рекурсии, максимальную глубину стека интерпретатора Python. Это ограничение предотвращает переполнение стека C в бесконечной рекурсии и сбой Python. Это может быть установлено с помощью setrecursionlimit().
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 Killer.
Из bash вы можете увидеть и установить ограничение стека (в килобайтах) с помощью:
ulimit -s
ulimit -s 10000
Значение по умолчанию для меня 8Mb.
Смотрите также:
- Установка размера стека в скрипте Python
- Python: Каков жесткий предел рекурсии для Linux, Mac и Windows?
Протестировано на Ubuntu 16.10, Python 2.7.12.
Используйте язык, который гарантирует оптимизацию хвостового вызова. Или используйте итерацию. В качестве альтернативы, будьте милыми с декораторами.
Я понимаю, что это старый вопрос, но для тех, кто читает, я бы рекомендовал не использовать рекурсию для таких проблем - списки намного быстрее и полностью избегают рекурсии. Я бы реализовал это как:
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.)
У меня была похожая проблема с ошибкой "Максимальная глубина рекурсии превышена". Я обнаружил, что ошибка вызывается поврежденным файлом в каталоге, который я зацикливал на os.walk. Если у вас возникли проблемы с решением этой проблемы и вы работаете с путями к файлам, обязательно сузьте их, так как это может быть поврежденный файл.
Конечно, числа Фибоначчи можно вычислить в 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) до этого значения.
Если вы хотите получить только несколько чисел Фибоначчи, вы можете использовать матричный метод.
from numpy import matrix
def fib(n):
return (matrix('0 1; 1 1', dtype='object') ** n).item(1)
Это быстро, поскольку NumPy использует быстрый алгоритм возведения в степень. Вы получите ответ в O(войдите n). И это лучше, чем формула Бине, потому что она использует только целые числа. Но если вы хотите, чтобы все числа Фибоначчи были до n, то лучше сделать это путем запоминания.
RecursionError: максимальная глубина рекурсии превышена при сравнении
Решение :
Во-первых, лучше знать, когда вы выполняете рекурсивную функцию в Python на большом вводе (> 10^4), вы можете столкнуться с «ошибкой превышения максимальной глубины рекурсии».
В модуле sys в Python есть функция getrecursionlimit(), которая может отображать ограничение рекурсии в вашей версии Python.
import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())
По умолчанию в одной версии Python установлено значение 1000, а в другой - 1500.
Вы можете изменить это ограничение, но очень важно знать, что если вы его сильно увеличите, у вас будет ошибка переполнения памяти.
Так что будьте осторожны, прежде чем увеличивать его. Вы можете использовать setrecursionlimit(), чтобы увеличить это ограничение в Python.
import sys
sys.setrecursionlimit(3000)
Пожалуйста, перейдите по этой ссылке для получения дополнительной информации о некоторых причинах этой проблемы:
Мы можем сделать это, используя @lru_cache декоратор и setrecursionlimit() метод:
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))
Выход
3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125
Источник
Использовать генераторы?
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
Как предложил@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
Я хотел бы привести пример использования запоминания для вычисления Фибоначчи, поскольку это позволит вам вычислять значительно большие числа с помощью рекурсии:
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))
Это все еще рекурсивно, но использует простую хеш-таблицу, которая позволяет повторно использовать ранее вычисленные числа Фибоначчи, а не делать их снова.
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))
Многие рекомендуют, чтобы увеличение предела рекурсии было хорошим решением, но это не так, потому что всегда будет ограничение. Вместо этого используйте итеративное решение.
def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(5)
Я не уверен, что повторяю кого-то, но некоторое время назад какая-то добрая душа написала Y-оператор для рекурсивно вызываемой функции, например:
def tail_recursive(func):
y_operator = (lambda f: (lambda y: y(y))(lambda x: f(lambda *args: lambda: x(x)(*args))))(func)
def wrap_func_tail(*args):
out = y_operator(*args)
while callable(out): out = out()
return out
return wrap_func_tail
а затем рекурсивной функции нужна форма:
def my_recursive_func(g):
def wrapped(some_arg, acc):
if <condition>: return acc
return g(some_arg, acc)
return wrapped
# and finally you call it in code
(tail_recursive(my_recursive_func))(some_arg, acc)
для чисел Фибоначчи ваша функция выглядит так:
def fib(g):
def wrapped(n_1, n_2, n):
if n == 0: return n_1
return g(n_2, n_1 + n_2, n-1)
return wrapped
print((tail_recursive(fib))(0, 1, 1000000))
выход:
..684684301719893411568996526838242546875
(на самом деле тонны цифр)
Мы также можем использовать вариант динамического программирования снизу вверх.
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))