这里有一个尾递归函数

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


当前回答

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

其他回答

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

当然,斐波那契数可以用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)值。

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

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

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

import sys
sys.setrecursionlimit(1500)