如何通过记忆使递归 fib 函数 return 成为正确的值

Question

我正在学习递归函数中的记忆，并在 Youtube 上偶然发现了斐波那契示例。我从未见过此人运行代码，所以也许他写错了。

当我复制代码并尝试运行时，我首先得到一个错误，因为我声明了没有范围的备忘录，所以我只是将范围设置为输入 + 1（因为我不是使用 0-index) 从而解决了这个问题。但现在我陷入了错误的 return 值。

def fib(num, memo=[]):
    if num == 0:
        return 0
    elif num == 1 or num == 2:
        return 1
    elif memo[num] != None:
        return memo[num]
    else:
        memo[num] = fib(num-1, memo) + fib(num-2, memo)
        return memo[num]

uInput = int(input("Fibonacci: "))
memo = list(range(uInput + 1))
fibNum = fib(uInput, memo)

print(fibNum)

上面的代码没有抛出任何错误，只是 return 是 "uInput" 值。因此，如果我输入 6，对于第 6 个斐波那契数，程序 returns 6 而不是 8，这是实际的第 6 个数。我不知道为什么会这样。

当我用谷歌搜索这个问题时，我发现了建议使用字典而不是列表的线程。如果那是唯一的方法，那也没关系。但是如果有办法让它与列表一起工作，我想了解它是如何完成的，以便我理解为什么我运行会遇到这个问题。

Answer 1

您用 list(range(uInput + 1)) 填充了 memo 列表。然后您的函数测试 memo[num] != None，它必须为真。所以它总是 return memo[num]，从而返回由 range 函数放入 memo 列表中的数字。

你应该删除这一行

memo = list(range(uInput + 1))

调用函数时只传递第一个参数。

Answer 2

访问 memo[num] 永远不会 return None。如果 num 超出范围，将引发 IndexError。此外，您通常不想将 memo 参数传递给您的函数，而是让它依赖于它自己的 memo 对象。

在您的情况下，您想检查索引是否在 len 的范围内。每当 num 超出范围时，必须递归计算输出并记忆。才可以returned.

def fib(num, memo=[0, 1]):
    if num >= len(memo):
        memo.append(fib(num - 1) +  fib(num - 2))
    return memo[num]

print(fib(10)) # 55

顺便说一句，上面的内容可以很容易地转换为迭代函数，通常在 Python 中效率更高。

def fib(num, memo=[0, 1]):
    while num >= len(memo):
        memo.append(memo[-1] + memo[-2])
    return memo[num]

Answer 3

这里有一个错误：

memo = list(range(uInput + 1))  # wrong

memo 应在索引 i 处包含 None，每个结果 fib(i) 尚未计算：

memo = [None] * (uInput + 1)  # right

可以将memo初始化为序列0,1的开头，这样可以简化函数：

def fib(num, memo):
    if memo[num] is None:
       memo[num] = fib(num-1, memo) + fib(num-2, memo)
    return memo[num]

uInput = int(input("Fibonacci: "))
memo = [0,1] + [None]*uInput
fibNum = fib(uInput, memo)

print(fibNum)

更新：

原代码中还有一个错误：memo是必填参数，一般情况下不能使用默认值。

Answer 4

我相信你的问题很好地论证了为什么记忆应该作为装饰器而不是与函数本身交织在一起:

from functools import lru_cache

@lru_cache()
def fibonacci(number):
    if number == 0:
        return 0

    if number == 1 or number == 2:
        return 1

    return fibonacci(number - 1) + fibonacci(number - 2)

uInput = int(input("Fibonacci: "))

fibNum = fibonacci(uInput)

print(fibNum)

否则你正在尝试同时调试两个不同的程序。使用和不使用 @lru_cache() 装饰器时输入 100 尝试上面的操作。

当然，这仍然受限于 Python 调用堆栈深度的相对较小的输入。有迭代（甚至更好的递归）算法可以做得更好。

如何通过记忆使递归 fib 函数 return 成为正确的值

How to make a recursive fib-function return the correct value with memoization

python

recursion

memoization

fibonacci