这里有一个尾递归函数
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，最好是死记硬背。
其他回答
看起来你只需要设置一个更高的递归深度:
import sys
sys.setrecursionlimit(1500)
资源。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上测试。
我想给你一个使用内存计算斐波那契的例子，因为这将允许你使用递归计算更大的数字:
cache = {}
def fib_dp(n):
if n in cache:
return cache[n]
if n == 0: return 0
elif n == 1: return 1
else:
value = fib_dp(n-1) + fib_dp(n-2)
cache[n] = value
return value
print(fib_dp(998))
这仍然是递归的，但是使用了一个简单的哈希表，允许重用以前计算的斐波那契数，而不是重新计算。
当然，斐波那契数可以用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
