这里有一个尾递归函数
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:在比较中超过了最大递归深度。这只是一个堆栈溢出吗?有办法绕过它吗?
这里有一个尾递归函数
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:在比较中超过了最大递归深度。这只是一个堆栈溢出吗?有办法绕过它吗?
当前回答
我们还可以使用一种自底向上的动态规划方法
def fib_bottom_up(n):
bottom_up = [None] * (n+1)
bottom_up[0] = 1
bottom_up[1] = 1
for i in range(2, n+1):
bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]
return bottom_up[n]
print(fib_bottom_up(20000))
其他回答
看起来你只需要设置一个更高的递归深度:
import sys
sys.setrecursionlimit(1500)
这是为了避免堆栈溢出。Python解释器限制了递归的深度,以帮助您避免无限递归,从而导致堆栈溢出。 尝试增加递归限制(sys.setrecursionlimit)或重写不使用递归的代码。
来自Python文档:
sys.getrecursionlimit () 返回递归限制的当前值,即Python解释器堆栈的最大深度。这个限制可以防止无限递归导致C堆栈溢出和Python崩溃。可以通过setrecursionlimit()来设置。
是的,它是防止堆栈溢出的一种方法。Python(或者更确切地说,CPython实现)没有优化尾部递归,并且无限制的递归会导致堆栈溢出。你可以用sys.getrecursionlimit检查递归限制:
import sys
print(sys.getrecursionlimit())
并使用sys.setrecursionlimit更改递归限制:
sys.setrecursionlimit(1500)
但这样做是危险的——标准限制有点保守,但Python的堆栈框架可能相当大。
Python不是函数式语言,尾递归也不是一种特别有效的技术。如果可能的话,迭代地重写算法通常是一个更好的主意。
当然,斐波那契数可以用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