我有以下练习:
'''FIBONACCI
Compute the n'th Fibonacci number fib(n), defined recursively:
fib(0) == 0, fib(1) == 1, fib(n) = fib(n - 1) + fib(n - 2)
Input:
A single line containing an integer n, 0 <= n <= 10.000
Output:
A single line with the integer fib(n).
Example:
Input: 10
Output: 55
'''
我的原始尝试可以这么说:
def fib(n):
if n <= 1:
return n
if n >= 2:
return fib(n-1) + fib(n-2)
n = int(input()) # Read integer n from standard input
print(fib(n))
然而，在达到最大递归深度之前，这段代码只能处理大约n=500。 为了增加这个数字，并创建最多可以处理10000个代码，我尝试了两件事:1）增加最大递归深度，2）以装饰器的形式使用记忆。现在代码可以处理大约n=2000:
import sys
from functools import lru_cache
sys.setrecursionlimit(10000)
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
if n >= 2:
return fib(n-1) + fib(n-2)
n = int(input()) # Read integer n from standard input
print(fib(n))
使用n>； 2000我得到一个内存错误（堆栈溢出）。 我该怎么解决这个问题？ 我还能做什么？ 我的递归函数是否有可能，或者我必须以某种方式改变它才能使它工作？ 如有帮助，不胜感激！
N第Fibonacci数的简单实现。 不需要使用递归。
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
fa, fb = 0, 1
for i in range(2, n + 1):
fa, fb = fb, fa + fb
return fb
使用递归实现时，当您试图深入到如此之深的地方时，您几乎会遇到麻烦。 就像@Alaniwi所说的那样，您总是可以用非递归方法实现它。 这里有一个O(n)时间解，具有O(1)空间复杂度。 （注意:理论上，您甚至可以得到o(logn)解决方案。）
from collections import deque
def fib(n):
past = deque([1], maxlen=2)
for _ in range(n): past.appendleft(sum(past))
return past[0]
因为fibonacci函数只需要f的最后两个值，所以我们只能存储那些并且向上冒泡。
在任务中，他们给出了fibonacci序列的递归定义，但没有提到递归实现。 这是递归定义的迭代实现:
def fib(n):
f1, f2 = 0, 1
for i in range(n + 1):
f1, f2 = f2, f1 + f2
return f2
