这里有一个尾递归函数
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:在比较中超过了最大递归深度。这只是一个堆栈溢出吗?有办法绕过它吗?
当前回答
当然,斐波那契数可以用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)值。
其他回答
编辑: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生成器导论。
看起来你只需要设置一个更高的递归深度:
import sys
sys.setrecursionlimit(1500)
我们还可以使用一种自底向上的动态规划方法
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)
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,最好是死记硬背。