这里有一个尾递归函数
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生成器导论。
是的，它是防止堆栈溢出的一种方法。Python(或者更确切地说，CPython实现)没有优化尾部递归，并且无限制的递归会导致堆栈溢出。你可以用sys.getrecursionlimit检查递归限制:
import sys
print(sys.getrecursionlimit())
并使用sys.setrecursionlimit更改递归限制:
sys.setrecursionlimit(1500)
但这样做是危险的——标准限制有点保守，但Python的堆栈框架可能相当大。
Python不是函数式语言，尾递归也不是一种特别有效的技术。如果可能的话，迭代地重写算法通常是一个更好的主意。
许多人建议增加递归限制是一个很好的解决方案，但它不是，因为总是会有限制。相反，使用迭代解决方案。
def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(5)
我想给你一个使用内存计算斐波那契的例子，因为这将允许你使用递归计算更大的数字:
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))
这仍然是递归的，但是使用了一个简单的哈希表，允许重用以前计算的斐波那契数，而不是重新计算。
