python 递归限制

Python08

python 递归限制,第1张

python不能无限的递归调用下去。并且当输入的值太大，递归次数太多时，python 都会报错

首先说结论，python解释器这么会限制递归次数，这么做为了避免"无限"调用导致的堆栈溢出。

tail recursion 就是指在程序最后一步执行递归。这种函数称为 tail recursion function。举个例子：

这个函数就是普通的递归函数，它在递归之后又进行了 乘 的操作。 这种普通递归，每一次递归调用都会重新推入一个调用堆栈。

把上述调用改成 tail recursion function

tail recursion 的好处是每一次都计算完，将结果传递给下一次调用，然后本次调用任务就结束了，不会参与到下一次的递归调用。这种情况下，只重复用到了一个堆栈。因此可以优化结构。就算是多次循环，也不会出现栈溢出的情况。这就是 tail recursion optimization 。

c和c++都有这种优化， python没有，所以限制了调用次数，就是为了防止无限递归造成的栈溢出。

如果递归次数过多，导致了开头的报错，可以使用 sys 包手动设置recursion的limit

手动放大 recursionlimit 限制：

在python里递归最多达到多少次？因为在跑程序的时候，次数有时多有时少，以前没有想过这个问题。那就自己动手在验证验证， 代码如下：

def recursion(n): 

    if(n <= 0): 

        return

    print n 

    recursion(n - 1) 

  

if __name__ == "__main__":

    recursion(1000)

当在我自己的机器运行以上代码时，发现最多能打印到998，然后就会抛出 “RuntimeError: maximum recursion

depth exceeded” 的错误了。

嘿，还真有限制。但转念一想，python不会这么弱吧。经过一番查找，发现这是python专门设置的一种机制用来防止无限递归造成Python溢出崩

溃， 最大递归次数是可以重新调整的。

（http://docs.python.org/2/library/sys.html#sys.setrecursionlimit），修改代码如

下：

import sys

sys.setrecursionlimit(1500)  # set the maximum depth as 1500

  

def recursion(n): 

    if(n <= 0): 

        return

    print n 

    recursion(n - 1) 

  

if __name__ == "__main__":

    recursion(1200)

再次运行，顺利通过！

def Sum(m):

    #函数返回两个值：递归次数，所求的值

    if m==1:return 1,m

    return 1+Sum(m-1)[0],m+Sum(m-1)[1]

cishu=Sum(10)[0]   

print cishu

>>>def Sum(m,n=1):

... if m==1:return n,m

... return n,m+Sum(m-1,n+1)[1]

>>>print Sum(10)[0]

10

>>>print Sum(5)[0]

5