如何使递归的fib函数通过memoization返回正确的值

Question

我正在学习递归函数中的memoization，偶然发现了Youtube上的fibonacci示例。我从未见过这个人运行代码，所以也许他写错了。

当我复制代码并尝试运行它时，我首先得到一个错误，因为我声明没有范围的备忘录，所以我只是将范围设置为输入+ 1（因为我没有使用0索引）因此解决了那个问题。但现在我陷入了错误的回报价值。

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)

上面的代码不会引发错误，只是返回“uInput”值。因此，如果我输入6，对于第6个斐波纳契数，程序返回6而不是8，这是实际的第6个数字。我不知道为什么会这样。

当我用google搜索问题时，我发现线程建议使用dicts而不是列表。如果这是唯一的方法，这一切都很好。但是如果有一种方法可以使它与列表一起工作，我想了解这是如何完成的，以便我理解为什么我会遇到这个问题。

Answer 1

这里有一个错误：

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

memo应包含指数None的i，每个结果fib(i)尚未计算：

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

备忘录可以初始化到序列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 2

我相信你的问题是一个很好的论据，为什么memoization应该作为装饰器应用而不是与函数本身交织在一起：

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)

否则，您正在尝试同时调试两个不同的程序。尝试上面输入100，有和没有@lru_cache()装饰器。

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