使用递归时如何避免内存错误？（斐波那契数字）

debugcn 发表于 Dev

雅可比曼

我有以下练习：

'''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斐波那契数的简单实现。无需使用递归。

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

（注意：这不是最快的。它是O（n）。可以使用O（log n）解决方案-例如，在这里，请参见其方法5。）

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。