这里有一个尾递归函数
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:在比较中超过了最大递归深度。这只是一个堆栈溢出吗?有办法绕过它吗?
当前回答
如果你只想得到很少的斐波那契数，你可以使用矩阵法。
from numpy import matrix
def fib(n):
return (matrix('0 1; 1 1', dtype='object') ** n).item(1)
它的速度很快，因为numpy使用了快速求幂算法。结果是O(log n)比比奈公式好因为它只使用整数。但如果你想让所有的斐波那契数都不超过n，最好是死记硬背。
其他回答
我有一个类似的问题，错误“最大递归深度超过”。我发现这个错误是由我用os.walk循环遍历的目录中的一个损坏文件触发的。如果您在解决这个问题时遇到了困难，并且您正在使用文件路径，请务必缩小范围，因为它可能是一个损坏的文件。
正如@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)
def fib(n, sum):
if n < 1:
return sum
else:
return fib(n-1, sum+n)
c = 998
print(fib(c, 0))
如果你只想得到很少的斐波那契数，你可以使用矩阵法。
from numpy import matrix
def fib(n):
return (matrix('0 1; 1 1', dtype='object') ** n).item(1)
它的速度很快，因为numpy使用了快速求幂算法。结果是O(log n)比比奈公式好因为它只使用整数。但如果你想让所有的斐波那契数都不超过n，最好是死记硬背。
使用一种保证尾部调用优化的语言。或者使用迭代。或者，和装饰师一起玩。
