python - 为什么这个函数在重复调用时返回不同的值？

Question

memory = {}
def rec(n):
    if n in memory:
        value = n
    elif n == 1:
        value = 1
    elif n == 2:
        value = 1
    elif n > 2:
        value = rec(n - 2) + rec(n - 1)
    memory[n] = value
    return value

这是代码，我知道它不完全是正确的递归代码。我不明白的是，如果我调用 rec(5)，第一次输出 7，下次输出 5。有人可以帮我解释一下吗？

Answer 1

你的问题是当 n 已经在内存中时你正在更新内存。你的第一个 rec(5) 的整个过程是:

rec(5) = rec(3) + rec(4) = rec(1) + rec(2) + rec(4) = 1 + 1 + rec(2) + rec(3)

到这里一切都是正确的。然后您的方法将计算 rec(2)，其中 2 已经在您的 memory 中，因此 rec(2) 的新值为 2。

如果你不明白为什么，请看这里:

def rec(n):
    if n in memory:
        value = n
    # ...
    memory[n] = value
    return value

然后计算rec(3)的值，3也在内存中，所以rec(3)现在是3

然后 rec(5) = 1 + 1 + 2 + 3 = 7

第二次运行，由于5在内存中，所以输出为5。

一种可能的解决方案:

def rec(n):
    if n in memory:
        return memory[n]
    elif n == 1:
        value = 1
    elif n == 2:
        value = 1
    elif n > 2:
        value = rec(n - 2) + rec(n - 1)
    memory[n] = value
    return value