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

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。请问有人能帮我解释一下吗？

- joijioj

---

你能否清楚地陈述你的问题？我不确定问题出在哪里... - tahesse

@intentionallyleftblank 这里本来有内容，但由于格式问题，<memory 没有显示出来 ;) - hellow

为什么这段代码第一次输出7？ - joijioj

使用rec(5)调用函数并输出7。我不理解这个。 - joijioj

@joijioj 请查看我回答中的解释。 - Nordle

它返回不同的结果，因为它使用全局变量“memory”来存储一些状态。 - zvone

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已经在你的内存中，因此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

- Kevin Fang

---

这很清晰，兄弟。我一直在更新内存，无论以前是否使用过它。非常感谢你！ - joijioj

@joijioj 不用担心。下次你遇到这种错误时，可以将重要的变量（在本例中是“memory”）打印出来，然后你就可以自己进行调试了。 - Kevin Fang

Answer 2

memory = {}
def rec(n):
    if n in memory:
        value = 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

print (rec(5))
print (rec(5))

现在它两次都打印5。问题出在value=n上，而应该是：

value=memory[n], 

所以，

value=n 

这意味着2的值也会被更新为2。

- Ashutosh Chapagain