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

Question

我有以下练习：

'''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 时，出现内存错误（堆栈溢出）。我该如何解决？我还能做什么？我的递归函数是否有可能，或者我是否必须以某种方式更改它才能使其工作？感谢您的帮助！

Answer 1

第 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) 的解决方案可用-- 例如 here，参见他们的方法 5。）

Answer 2

使用递归实现，当你试图深入到如此深的层次时，你几乎会遇到麻烦。正如@alaniwi 所说，您始终可以用非递归方法实现它。这是具有 O(1) space 复杂度的 O(n) 时间解决方案。（注意：理论上你甚至可以获得 O(log n) 的解决方案。）

from collections import deque

def fib(n):
    past = deque([1], maxlen=2)
    for _ in range(n): past.appendleft(sum(past))
    return past[0]

因为斐波那契函数只需要 f 的最后两个值，我们可以只存储那些和向上冒泡的值。

Answer 3

在任务中，他们给出了斐波那契数列的递归定义，但没有提及递归实现。这是递归定义的迭代实现：

def fib(n):
    if n == 0:
        return 0
    f1, f2 = 0, 1
    for i in range(1, n + 1):
        f1, f2 = f2, f1 + f2
    return f2

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

How to avoid memory error when using recursion? (Fibonacci Numbers)

python

recursion

memory-efficient

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

How to avoid memory error when using recursion? (Fibonacci Numbers)

python

recursion

memory-efficient

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