Python中的最大递归深度是多少,以及如何增加它？

Question

我在这里有这个尾递归函数:

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

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

它可以工作到n = 997,然后它就会中断并吐出"比较时超出的最大递归深度" RuntimeError.这只是一个堆栈溢出？有办法解决它吗？

Answer 1

这是一个防止堆栈溢出的防范,是的.Python(或者更确切地说,CPython实现)不优化尾递归,并且无限制的递归导致堆栈溢出.您可以使用更改递归限制sys.getrecursionlimit,但这样做很危险 - 标准限制有点保守,但Python堆栈框架可能非常大.

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

Answer 2

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

import sys
sys.setrecursionlimit(1500)

Answer 3

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

来自python网站:

sys.getrecursionlimit()

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

Answer 4

如果您经常需要更改递归限制(例如,在解决编程难题时),您可以定义一个简单的上下文管理器,如下所示:

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 5

使用保证尾调用优化的语言.或者使用迭代.或者,装饰可爱.

Answer 6

resource.setrlimit 还必须用于增加堆栈大小并防止段错误

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将耗尽,这将使你的计算机因交换疯狂而停止运行,或者通过OOM杀手杀死Python.

从bash中,您可以看到并设置堆栈限制(以kb为单位):

ulimit -s
ulimit -s 10000

我的默认值是8Mb.

也可以看看:

• 在python脚本中设置stacksize
• Python:Linux,Mac和Windows的硬递归限制是多少？

在Ubuntu 16.10,Python 2.7.12上测试过.

Answer 7

我意识到这是一个老问题但是对于那些阅读,我建议不要使用递归来解决这个问题 - 列表要快得多并且完全避免递归.我会实现这个:

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

Answer 8

当然,通过应用Binet公式,可以在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 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(log n) 中得到答案。它比比奈公式更好，因为它只使用整数。但是如果你想要所有的斐波那契数达到 n，那么最好通过记忆来完成。

Answer 11

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

来源

函数工具 lru_cache

Answer 12

RecursionError：比较中超出最大递归深度

\n

解决方案 ：

\n

首先，\xe2\x80\x99s 最好知道当你在 Python 中对大输入（> 10^4）执行递归函数时，你可能会遇到 \xe2\x80\x9cmaximum recursion Deepisoded 错误\xe2\x80\x9d 。

\n

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

\n

import sys\nprint("Python Recursive Limitation = ", sys.getrecursionlimit())\n

\n

Python 某些版本的默认值为 1000，其他版本的默认值为 1500

\n

您可以更改此限制，但\xe2\x80\x99s非常重要，要知道如果将其增加太多，则会出现内存溢出错误。

\n

所以增加之前要小心。您可以在 Python 中使用 setrecursionlimit() 来增加此限制。

\n

import sys\nsys.setrecursionlimit(3000)\n

\n

请点击此链接以获取有关导致此问题的原因的更多信息：

\n

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

\n

Answer 13

使用发电机？

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