Python中的最大递归深度是什么，如何增加它?

这里有一个尾递归函数

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


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

它运行到n=997，然后它就崩溃并吐出一个RecursionError: maximum recursion depth exceeded in comparison。这只是一个堆栈溢出吗?有办法绕过它吗?

883721 次浏览
小开

看起来你只需要设置更高的递归深度:

import sys
sys.setrecursionlimit(1500)
小开

这是为了避免堆栈溢出。Python解释器限制了递归的深度，以帮助您避免无限递归，从而导致堆栈溢出。 尝试增加递归限制(sys.setrecursionlimit)或重写不使用递归的代码

Python文档:

# EYZ0

返回递归限制的当前值，即Python解释器堆栈的最大深度。这个限制可以防止无限递归导致C堆栈溢出和Python崩溃。它可以通过setrecursionlimit()设置。

小开
最佳答案

是的，它是防止堆栈溢出的一种方法。Python(或者更确切地说，CPython实现)没有优化尾部递归，并且无限制的递归会导致堆栈溢出。你可以用sys.getrecursionlimit检查递归限制:

import sys
print(sys.getrecursionlimit())

并使用sys.setrecursionlimit更改递归限制:

sys.setrecursionlimit(1500)

但这样做是危险的——标准限制有点保守，但Python的堆栈框架可能相当大。

Python不是函数式语言，尾递归也不是一种特别有效的技术。如果可能的话，迭代地重写算法通常是一个更好的主意。

小开

使用一种保证尾部调用优化的语言。或者使用迭代。或者，用修饰符来表现可爱。

小开

我知道这是一个老问题，但对于那些阅读的人来说，我建议不要使用递归来解决这样的问题——列表要快得多，并且完全避免递归。我将这样实现:

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

(在xrange中使用n+1，如果你从0开始计数你的斐波那契数列，而不是从1开始。)

小开

我有一个类似的问题，错误“最大递归深度超过”。我发现错误是由我在os.walk循环的目录中的一个损坏的文件触发的。如果您在解决这个问题时遇到了困难，并且您正在使用文件路径，请务必缩小范围，因为它可能是一个损坏的文件。

小开

编辑:6年后，我意识到我的“使用发电机”;很轻率，没有回答问题。我的歉意。

我想我的第一个问题是:你真的需要改变递归限制吗?如果不是，那么也许我的答案或其他不涉及改变递归限制的答案将适用。否则，如前所述，使用sys.getrecursionlimit(n)覆盖递归限制。

使用发电机?

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()函数改编自Python生成器简介。

小开

当然，斐波那契数可以在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)到该值的所有值。

小开

许多人建议增加递归限制是一个很好的解决方案，但它不是，因为总是会有限制。相反，使用迭代解决方案。

def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(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
小开

resource.setrlimit还必须用于增加堆栈大小和防止段故障

Linux内核限制进程的堆栈。

Python将局部变量存储在解释器的堆栈上，因此递归占用解释器的堆栈空间。

如果Python解释器试图超过堆栈限制，Linux内核会使其出现分段错误。

堆栈限制大小由getrlimit和setrlimit系统调用控制。

Python通过resource模块提供了对这些系统调用的访问。

sys.setrecursionlimit提到过，例如https://stackoverflow.com/a/3323013/895245只增加了Python解释器自身对堆栈大小的限制，但它没有触及Linux内核对Python进程施加的限制。

示例程序:

main.py

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)

当然，如果你继续增加setrlimit，你的RAM最终会用完，这将使你的计算机由于疯狂的交换而变慢到停止，或者通过伯父杀手杀死Python。

在bash中，您可以使用以下命令查看并设置堆栈限制(单位为kb):

ulimit -s
ulimit -s 10000

我的默认值是8Mb。

参见:

在Ubuntu 16.10, Python 2.7.12上测试。

小开

如果你只想得到很少的斐波那契数，你可以使用矩阵法。

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


def __enter__(self):
self.old_limit = sys.getrecursionlimit()
sys.setrecursionlimit(self.limit)


def __exit__(self, type, value, tb):
sys.setrecursionlimit(self.old_limit)

然后调用具有自定义限制的函数，您可以这样做:

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

在退出with语句体时，递归限制将恢复到默认值。

附注:您可能还想增加Python进程的堆栈大小，以获得较大的递归限制值。例如，可以通过ulimit shell内置或limits.conf(5)文件来完成。

小开

我想给你一个使用内存计算斐波那契的例子，因为这将允许你使用递归计算更大的数字:

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

我们可以使用@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

源

functools lru_cache

小开

我们还可以使用一种自底向上的动态规划方法

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

我不确定我是不是在重复某人的意思但前段时间有人写了一个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

(实际上是数字的音调)

小开

RecursionError:在比较中超出的最大递归深度

解决方案:

首先，最好知道何时在Python中对大输入执行递归函数(>10^4)，你可能会遇到“最大递归深度超过错误”。

Python中的sys模块有一个函数getrecursionlimit()可以显示Python版本中的递归限制。

import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())

在某些版本的Python中，默认值是1000，而在另一些版本中则是1500

你可以改变这个限制，但重要的是要知道，如果你增加太多，就会出现内存溢出错误。

所以在增加它之前要小心。你可以使用setrecursionlimit()在Python中增加这个限制。

import sys
sys.setrecursionlimit(3000)

请点击此链接了解导致此问题的更多信息:

https://elvand.com/quick-sort-binary-search/


提交答案