斐波那契记忆法：无法理解TypeE的原因

Question

刚开始学习动态规划和记忆，以生成第n个Fibonacci数为例。我写了下面的代码（实际上从一个网站上获得了帮助），删除了它，并尝试自己写一次。我无法理解返回调用（TypeError）有一个问题。你知道吗

我将返回备忘录[x]调用缩进到if语句下面，程序就运行了。你知道吗

我只想知道以下代码中出现错误的原因：

代码是做什么的？你知道吗

1）创建一个函数来记忆输入函数

2）子函数“helper”，检查输入函数的输出是否在名为“memo”的字典中。如果没有，那么它会根据需要更新字典

整个函数从memo返回一个数字（如果它已经在memo中）以避免不必要的分支。你知道吗

3）使用递归算法创建生成斐波那契数的函数。你知道吗

4）记忆Fib编号生成器并打印第n个Fib编号

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
            return memo[x]
    return helper
def fib(n):
    if n==0:
        return 0
    if n == 1:
        return 1
    else:
        return fib(n-1)+fib(n-2)

fib = memoize(fib)

print(fib(10))

我希望它返回第n个Fib。不是，而是在返回备忘录[x]调用中返回错误。你知道吗

错误消息：

Traceback (most recent call last):
  File "E:\euler25.py", line 18, in <module>
    print(fib(10))
  File "E:\euler25.py", line 5, in helper
    memo[x] = f(x)
  File "E:\euler25.py", line 14, in fib
    return fib(n-1)+fib(n-2)
  File "E:\euler25.py", line 5, in helper
    memo[x] = f(x)
  File "E:\euler25.py", line 14, in fib
    return fib(n-1)+fib(n-2)
  File "E:\euler25.py", line 5, in helper
    memo[x] = f(x)
  File "E:\euler25.py", line 14, in fib
    return fib(n-1)+fib(n-2)
  File "E:\euler25.py", line 5, in helper
    memo[x] = f(x)
  File "E:\euler25.py", line 14, in fib
    return fib(n-1)+fib(n-2)
  File "E:\euler25.py", line 5, in helper
    memo[x] = f(x)
  File "E:\euler25.py", line 14, in fib
    return fib(n-1)+fib(n-2)
  File "E:\euler25.py", line 5, in helper
    memo[x] = f(x)
  File "E:\euler25.py", line 14, in fib
    return fib(n-1)+fib(n-2)
  File "E:\euler25.py", line 5, in helper
    memo[x] = f(x)
  File "E:\euler25.py", line 14, in fib
    return fib(n-1)+fib(n-2)
  File "E:\euler25.py", line 5, in helper
    memo[x] = f(x)
  File "E:\euler25.py", line 14, in fib
    return fib(n-1)+fib(n-2)
TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'
[Finished in 0.1s with exit code 1]

此错误消息是什么意思？你知道吗

Answer 1

memoization函数的return语句范围有问题：

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        # function should return always the memoized value
        return memo[x]
    return helper

问题是在某个时刻，helper函数返回一个None，这使得fib函数尝试在int和None之间+，这会触发TypeError

这是live example