这里有一个尾递归函数
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:在比较中超过了最大递归深度。这只是一个堆栈溢出吗?有办法绕过它吗?
当前回答
我想给你一个使用内存计算斐波那契的例子，因为这将允许你使用递归计算更大的数字:
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))
这仍然是递归的，但是使用了一个简单的哈希表，允许重用以前计算的斐波那契数，而不是重新计算。
其他回答
我知道这是一个老问题，但对于那些阅读的人来说，我建议不要使用递归来解决这样的问题——列表要快得多，并且完全避免递归。我将这样实现:
def fibonacci(n):
f = [0,1,1]
for i in xrange(3,n):
f.append(f[i-1] + f[i-2])
return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1])
(在xrange中使用n+1，如果你从0开始计数你的斐波那契数列，而不是从1开始。)
使用一种保证尾部调用优化的语言。或者使用迭代。或者，和装饰师一起玩。
这是为了避免堆栈溢出。Python解释器限制了递归的深度，以帮助您避免无限递归，从而导致堆栈溢出。 尝试增加递归限制(sys.setrecursionlimit)或重写不使用递归的代码。
来自Python文档:
sys.getrecursionlimit () 返回递归限制的当前值，即Python解释器堆栈的最大深度。这个限制可以防止无限递归导致C堆栈溢出和Python崩溃。可以通过setrecursionlimit()来设置。
我不确定我是不是在重复某人的意思但前段时间有人写了一个y算子用于递归调用函数
def tail_recursive(func):
y_operator = (lambda f: (lambda y: y(y))(lambda x: f(lambda *args: lambda: x(x)(*args))))(func)
def wrap_func_tail(*args):
out = y_operator(*args)
while callable(out): out = out()
return out
return wrap_func_tail
然后递归函数需要形式:
def my_recursive_func(g):
def wrapped(some_arg, acc):
if <condition>: return acc
return g(some_arg, acc)
return wrapped
# and finally you call it in code
(tail_recursive(my_recursive_func))(some_arg, acc)
对于斐波那契数，你的函数是这样的:
def fib(g):
def wrapped(n_1, n_2, n):
if n == 0: return n_1
return g(n_2, n_1 + n_2, n-1)
return wrapped
print((tail_recursive(fib))(0, 1, 1000000))
输出:
..684684301719893411568996526838242546875
(实际上是数字的音调)
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/
