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

问题: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。这仅仅是堆栈溢出吗?有办法解决吗?

I have this tail recursive function here:

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

It works up to n=997, then it just breaks and spits out a RecursionError: maximum recursion depth exceeded in comparison. Is this just a stack overflow? Is there a way to get around it?


回答 0

这是防止堆栈溢出的保护措施,是的。Python(或更确切地说,CPython实现)无法优化尾部递归,无限制的递归会导致堆栈溢出。您可以使用来检查递归限制,sys.getrecursionlimit并使用来更改递归限制sys.setrecursionlimit,但是这样做很危险-标准限制有些保守,但是Python堆栈框架可能会很大。

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

It is a guard against a stack overflow, yes. Python (or rather, the CPython implementation) doesn’t optimize tail recursion, and unbridled recursion causes stack overflows. You can check the recursion limit with sys.getrecursionlimit and change the recursion limit with sys.setrecursionlimit, but doing so is dangerous — the standard limit is a little conservative, but Python stackframes can be quite big.

Python isn’t a functional language and tail recursion is not a particularly efficient technique. Rewriting the algorithm iteratively, if possible, is generally a better idea.


回答 1

看起来您只需要设置更高的递归深度即可

import sys
sys.setrecursionlimit(1500)

Looks like you just need to set a higher recursion depth:

import sys
sys.setrecursionlimit(1500)

回答 2

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

Python文档中

sys.getrecursionlimit()

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

It’s to avoid a stack overflow. The Python interpreter limits the depths of recursion to help you avoid infinite recursions, resulting in stack overflows. Try increasing the recursion limit (sys.setrecursionlimit) or re-writing your code without recursion.

From the Python documentation:

sys.getrecursionlimit()

Return the current value of the recursion limit, the maximum depth of the Python interpreter stack. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. It can be set by setrecursionlimit().


回答 3

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

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语句主体退出时,递归限制将恢复为默认值。

If you often need to change the recursion limit (e.g. while solving programming puzzles) you can define a simple context manager like this:

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)

Then to call a function with a custom limit you can do:

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

On exit from the body of the with statement the recursion limit will be restored to the default value.


回答 4

使用保证尾叫优化的语言。或使用迭代。另外,也可以和装饰工一起变得可爱。

Use a language that guarantees tail-call optimisation. Or use iteration. Alternatively, get cute with decorators.


回答 5

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

Linux内核限制了进程的堆栈

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

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

堆栈限制大小由getrlimitsetrlimit系统调用控制。

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 Killer杀死Python。

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

ulimit -s
ulimit -s 10000

我的默认值为8Mb。

也可以看看:

已在Ubuntu 16.10,Python 2.7.12上测试。

resource.setrlimit must also be used to increase the stack size and prevent segfault

The Linux kernel limits the stack of processes.

Python stores local variables on the stack of the interpreter, and so recursion takes up stack space of the interpreter.

If the Python interpreter tries to go over the stack limit, the Linux kernel makes it segmentation fault.

The stack limit size is controlled with the getrlimit and setrlimit system calls.

Python offers access to those system calls through the resource module.

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)

Of course, if you keep increasing ulimit, your RAM will run out, which will either slow your computer to a halt due to swap madness, or kill Python via the OOM Killer.

From bash, you can see and set the stack limit (in kb) with:

ulimit -s
ulimit -s 10000

The default value for me is 8Mb.

See also:

Tested on Ubuntu 16.10, Python 2.7.12.


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

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

I realize this is an old question but for those reading, I would recommend against using recursion for problems such as this – lists are much faster and avoid recursion entirely. I would implement this as:

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

(Use n+1 in xrange if you start counting your fibonacci sequence from 0 instead of 1.)


回答 7

当然,可以通过应用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)

Of course Fibonacci numbers can be computed in O(n) by applying the Binet formula:

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

As the commenters note it’s not O(1) but O(n) because of 2**n. Also a difference is that you only get one value, while with recursion you get all values of Fibonacci(n) up to that value.


回答 8

错误“超出最大递归深度”时,我遇到了类似的问题。我发现错误是由我遍历的目录中的损坏文件触发的os.walk。如果您无法解决此问题,并且正在使用文件路径,请确保将其范围缩小,因为它可能是损坏的文件。

I had a similar issue with the error “Max recursion depth exceeded”. I discovered the error was being triggered by a corrupt file in the directory I was looping over with os.walk. If you have trouble solving this issue and you are working with file paths, be sure to narrow it down, as it might be a corrupt file.


回答 9

如果只想得到几个斐波那契数,则可以使用矩阵法。

from numpy import matrix

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

由于numpy使用快速指数运算算法,因此速度很快。您会在O(log n)中得到答案。它比Binet的公式更好,因为它仅使用整数。但是,如果您希望所有斐波那契数均不超过n,那么最好通过记忆来实现。

If you want to get only few Fibonacci numbers, you can use matrix method.

from numpy import matrix

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

It’s fast as numpy uses fast exponentiation algorithm. You get answer in O(log n). And it’s better than Binet’s formula because it uses only integers. But if you want all Fibonacci numbers up to n, then it’s better to do it by memorisation.


回答 10

使用生成器?

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

Use generators?

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

above fib() function adapted from: http://intermediatepythonista.com/python-generators


回答 11

正如@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

As @alex suggested, you could use a generator function to do this sequentially instead of recursively.

Here’s the equivalent of the code in your question:

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

回答 12

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

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(5)

Many recommend that increasing recursion limit is a good solution however it is not because there will be always limit. Instead use an iterative solution.

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(5)

回答 13

我想给你一个使用记忆来计算斐波那契的例子,因为这将允许您使用递归来计算更大的数字:

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

这仍然是递归的,但是使用了一个简单的哈希表,该哈希表允许重新使用先前计算的斐波那契数,而不是再次进行处理。

I wanted to give you an example for using memoization to compute Fibonacci as this will allow you to compute significantly larger numbers using recursion:

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

This is still recursive, but uses a simple hashtable that allows the reuse of previously calculated Fibonacci numbers instead of doing them again.


回答 14

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

回答 15

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

输出量

30024687611784610909954941797150256486927479374907929434683754295022302429422848358634023335752162178658116387303893522391813423077567204146193912177985425759965410810605019053021570190026149647173108088094786756027114403612415007326991458343778563263940370716662743216573053208040553070210197932517628308167015873869948880323622321982198435498652758806996123592751252434571324967728548865087033966433650424543330098020063842868595816492963908030032326548984645615892344451398632426062857115917462228808073910572119126558184997987209873025407120679598408021068497765475222474299046183573947717256532535593461952826012850191693602073551792238148571064052850079975476925463787570629995816578671884209957706505655213778743330859631234442589530527514612069776150795114358628796784390811755362655769771068650740995128972351005382411964458155682913778466563529792280989115666759565256441826456081786038371722278388967254256057199423000376505262314868810660373978669420138382967692847455277784392729950672314920693691302891547531323138832943985935078735556672110054220032041561548590315294621529531199575971957359536867988711311482550501404508450342400953050944499115785985396588557041582402218095280101794144934995834735688732530679216395139965967382758179096248575936932919808413032911456135664665752332836514201349157649613728759338222629534204445483491804365831832919448755994772408147745801871446379654872505781349904024433656779853884819614924449819945230342456197818533654765527194609607959296668836657042938973102012760116580743591941893596607924960274722264285715479716022598086974414353585784805898377669116842002756368891922547626785125970004526761913744759327966638428657446582649249137716764154041799200960747515164228729976654250474574283272762300592961327227879153001050020190062933200829553787159082636533777550311557940634505157310094024075846831328702063769940259207902985911442136599426686220621914413462000983429439551695225325742716449543602174724585214896718594652325684194041820439660922117443726997973759660480107754534446001535247722384014147895626514102898089949605331327595320928957794069409252529061666121536998507599337628979471759721478687840083202475862103785567113327394632779402552890479623233069460683818874460463877452479256752401829811908362649646406120699094586824433927299460840993120477529668064393314036639349699429580222379452059925811788036061569820343853471827665733517687496651725499086383376119531998081619378853667092850432765957264840681380911889146981517031227737267252613705423551621181643027288122591924764289387307241098259223319732561050912005515665813505080619227629100785282198699132141465755572491992636342411653522265707496189070505531154683066691844859102698062258945308098231022792317500616520425607725305767131486478587056496429077806032476806802362362202208266406656599026501804747607137957607601654671

资源

functools lru_cache

We can do that using @lru_cache decorator and setrecursionlimit() method:

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

Output

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125

Source

functools lru_cache


回答 16

我们还可以使用动态编程自底向上方法的变体

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

We could also use a variation of dynamic programming bottom up approach

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