这里有一个尾递归函数

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


当前回答

是的,它是防止堆栈溢出的一种方法。Python(或者更确切地说,CPython实现)没有优化尾部递归,并且无限制的递归会导致堆栈溢出。你可以用sys.getrecursionlimit检查递归限制:

import sys
print(sys.getrecursionlimit())

并使用sys.setrecursionlimit更改递归限制:

sys.setrecursionlimit(1500)

但这样做是危险的——标准限制有点保守,但Python的堆栈框架可能相当大。

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

其他回答

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

使用一种保证尾部调用优化的语言。或者使用迭代。或者,和装饰师一起玩。

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

编辑: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生成器导论。