这里有一个尾递归函数

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:在比较中超过了最大递归深度。这只是一个堆栈溢出吗?有办法绕过它吗?


当前回答

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

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开始。)

其他回答

编辑: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)值。

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

解决方案:

首先,最好知道当你在一个大输入(> 10^4)上用Python执行递归函数时,你可能会遇到“最大递归深度超出错误”。

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/

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

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开始。)

资源。Setrlimit还必须用于增加堆栈大小和防止段故障

Linux内核限制了进程的堆栈。

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

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

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

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

sys。例如,https://stackoverflow.com/a/3323013/895245中提到的setrecursionlimit只增加了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最终会用完,这将使你的计算机由于疯狂的交换而变慢到停止,或者通过OOM杀手杀死Python。

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

ulimit -s
ulimit -s 10000

我的默认值是8Mb。

参见:

在python脚本中设置stacksize Linux、Mac和Windows的硬递归限制是什么?

在Ubuntu 16.10, Python 2.7.12上测试。