您应该
memo[n]始终返回，不仅要进行不安全的查找（的最后一行
fastFib()）：
def fastFib(n, memo): global numCalls numCalls += 1 print 'fib1 called with', n if not n in memo: memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo) #this should be outside of the if clause: return memo[n] #<<<<<< THIS
这样可以减少调用次数，因为对于
n您的每个值，实际上最多只能计算和递归一次，从而将递归调用的次数限制为
O(n)（
2n调用上限），而不必一次又一次地有效地重新计算相同的值进行指数递归调用。
fib（5）的一个小例子，其中每一行都是递归调用：
天真的方法：
f(5) = f(4) + f(3) = f(3) + f(2) + f(3) =f(2) + f(1) + f(2) + f(3) =f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) = 1 + f(0) + f(1) + f(2) + f(3) = 2 + f(1) + f(2) + f(3) =3 + f(2) + f(3) = 3 + f(1) + f(0) + f(3) = 3 + 1 + f(0) + f(3) = 5 + f(3) = 5 + f(2) + f(1) =5 + f(1) + f(0) + f(1) =5 + 1 + f(0) + f(1) =5 + 2 + f(1) =8
现在，如果您使用备忘录，则无需重新计算很多事情（例如
f(2)，它被计算了3次），您将获得：
f(5) = f(4) + f(3) = f(3) + f(2) + f(3) =f(2) + f(1) + f(2) + f(3) =f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) = 1 + f(0) + f(1) + f(2) + f(3) = 2 + f(1) + f(2) + f(3) =3 + f(2) + f(3) = {f(2) is already known}3 + 2 + f(3) = {f(3) is already known}5 + 3 = 8如您所见，第二个比第一个短，并且数字（
n）越大，该差异就越大。
