我在这里有这个尾递归函数:
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
。这只是堆栈溢出吗?有没有办法绕过它?
line <n>, in <module>
),此代码为 n=1
占用 2 个堆栈帧(因为基本情况是 n < 1
,所以对于 n=1
它仍然递归)。而且我猜递归限制不包括在内,因为它是“当你达到 1000 时出错”而不是“如果你超过 1000 (1001) 时出错”。 997 + 2
小于 1000,所以它可以工作 998 + 2
不是因为它达到了限制。
recursive_function(997)
有效,它在 998
处中断。当您调用 recursive_function(998)
时,它使用 999 个堆栈帧,并且解释器添加了 1 个帧(因为您的代码总是像它是顶级模块的一部分一样运行),这使得它达到了 1000 个限制。
它可以防止堆栈溢出,是的。 Python(或者更确切地说,CPython 实现)不会优化尾递归,并且肆无忌惮的递归会导致堆栈溢出。您可以使用 sys.getrecursionlimit
检查递归限制:
import sys
print(sys.getrecursionlimit())
并使用 sys.setrecursionlimit
更改递归限制:
sys.setrecursionlimit(1500)
但这样做很危险——标准限制有点保守,但 Python 堆栈帧可能非常大。
Python 不是一种函数式语言,尾递归也不是一种特别有效的技术。如果可能,迭代地重写算法通常是一个更好的主意。
看起来您只需要 set a higher recursion depth:
import sys
sys.setrecursionlimit(1500)
这是为了避免堆栈溢出。 Python 解释器限制了递归的深度,以帮助您避免无限递归,从而导致堆栈溢出。尝试增加递归限制 (sys.setrecursionlimit
) 或在不使用递归的情况下重新编写代码。
sys.getrecursionlimit() 返回递归限制的当前值,Python 解释器堆栈的最大深度。此限制可防止无限递归导致 C 堆栈溢出和 Python 崩溃。它可以通过 setrecursionlimit() 设置。
如果您经常需要更改递归限制(例如在解决编程难题时),您可以定义一个简单的 context manager,如下所示:
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
语句的主体退出时,递归限制将恢复为默认值。
PS您可能还想为递归限制的大值增加 Python 进程的堆栈大小。例如,这可以通过 ulimit
shell 内置文件或 limits.conf(5)
文件来完成。
resource
。没有它,你会得到一个分段错误,如果你 setrecursionlimit
太高并尝试使用新的限制(大约 8 兆字节的堆栈帧,使用简单函数转换为约 30,000 个堆栈帧),整个 Python 进程将崩溃上面,在我的笔记本电脑上)。
resource.setrlimit
还必须用于增加堆栈大小并防止段错误
Linux 内核 limits the stack of processes。
Python 将局部变量存储在解释器的堆栈中,因此递归占用了解释器的堆栈空间。
如果 Python 解释器试图超过堆栈限制,Linux 内核会使其分段错误。
堆栈限制大小由 getrlimit
和 setrlimit
系统调用控制。
Python 通过 resource
模块提供对这些系统调用的访问。
例如在 https://stackoverflow.com/a/3323013/895245 中提到的 sys.setrecursionlimit
仅增加了 Python 解释器自身对其自身堆栈大小施加的限制,但并未触及 Linux 内核对 Python 进程施加的限制。
示例程序:
主文件
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 最终会耗尽,这会导致您的计算机因交换疯狂而停止运行,或者通过 OOM Killer 杀死 Python。
在 bash 中,您可以使用以下命令查看和设置堆栈限制(以 kb 为单位):
ulimit -s
ulimit -s 10000
我的默认值为 8Mb。
也可以看看:
在 python 脚本中设置堆栈大小
Linux、Mac 和 Windows 的硬递归限制是多少?
在 Ubuntu 16.10、Python 2.7.12 上测试。
使用保证尾调用优化的语言。或者使用迭代。或者,使用 decorators 变得可爱。
ulimit -s
个堆栈帧,否则它是 stackoverflow.com/a/50120316
我意识到这是一个老问题,但对于那些阅读的人,我建议不要对此类问题使用递归 - 列表要快得多并且完全避免递归。我将其实现为:
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])
(如果您从 0 而不是 1 开始计算斐波那契数列,则在 xrange 中使用 n+1。)
xrange
简称为 range
。
我遇到了与错误“超出最大递归深度”类似的问题。我发现错误是由我用 os.walk
循环的目录中的损坏文件触发的。如果您在解决此问题时遇到问题并且正在使用文件路径,请务必缩小范围,因为它可能是损坏的文件。
当然,斐波那契数可以通过应用 Binet formula 在 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))
正如评论者所指出的,由于 2**n
,它不是 O(1) 而是 O(n)。另外一个区别是您只能获得一个值,而通过递归您可以获得 Fibonacci(n)
的所有值直到该值。
n
会失败 - (1+sqrt(5))**n
和 (1+sqrt(5))**(n+1)
之间的差异小于 1 ulp,因此您开始得到不正确的结果。
2**n
实际上是 O(log(n))。
如果你只想得到几个斐波那契数,你可以使用矩阵方法。
from numpy import matrix
def fib(n):
return (matrix('0 1; 1 1', dtype='object') ** n).item(1)
numpy 使用快速求幂算法很快。你得到 O(log n) 的答案。它比比内公式更好,因为它只使用整数。但是,如果您希望所有斐波那契数都达到 n,那么最好通过记忆来完成。
作为@alex suggested,您可以使用generator function 按顺序而不是递归地执行此操作。
这是您问题中代码的等价物:
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
我们可以使用 @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
资源
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/
编辑: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()
函数改编自 Introduction to Python Generators。
[fibs().next() for ...]
每次都会生成一个新生成器。
islice
docs.python.org/3/library/itertools.html#itertools.islice 从您的生成器中获取元素。
islice
需要如下所示(对于第 1001 个数字):value = next(islice(fib(), 1000, 1001))
。
许多人建议增加递归限制是一个很好的解决方案,但这并不是因为总会有限制。而是使用迭代解决方案。
def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(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))
我们还可以使用动态规划自下而上方法的变体
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
(实际上是数字的音调)
不定期副业成功案例分享
sys
和resource
模块中的限制:stackoverflow.com/a/16248113/205521