我写了两个fibonacci函数，一个是使用递归，正如预期的那样，fibonacci_recrasive(4(在调用堆栈中有9个函数调用：
def fibonacci_recursive_1(n):
if n == 0 or n == 1: # base case
result = n
print('return from base case, n = ', n, ', fib({}) = '.format(n), result)
return result
else: # recursive case
result = fibonacci_recursive_1(n-2) + fibonacci_recursive_1(n-1)
print('return from recursive case, n = ', n, ', fib({}) = '.format(n), result)
return result
fibonacci_recursive_1(4)
从基本情况返回，n=0，fib(0(=0
从基本情况返回，n=1，fib(1(=1
递归情况返回，n=2，fib(2(=1
从基本情况返回，n=1，fib(1(=1
从基本情况返回，n=0，fib(0(=0
从基本情况返回，n=1，fib(1(=1
递归情况返回，n=2，fib(2(=1
递归情况返回，n=3，fib(3(=2
递归情况返回，n=4，fib(4(=3
3
然后我做了一个动态编程记忆
stored_results = {}
def fibonacci_dynamic_1(n):
result = 0
if n in stored_results: # memoization
result += stored_results[n]
print('return from cached results, n = ', n, ', fib({}) = '.format(n), result)
return result
else:
if n == 0 or n == 1: # base case
result = n
stored_results[n] = result
print('return from base case, n = ', n, ', fib({}) = '.format(n), result)
return result
else: # recursive case
result = fibonacci_dynamic_1(n-2) + fibonacci_dynamic_1(n-1)
stored_results[n] = result
print('return from recursive case, n = ', n, ', fib({}) = '.format(n), result)
return result
fibonacci_dynamic_1(4)
令我惊讶的是，fibonacci_dynamic(4(的调用堆栈中只剩下7个函数调用：
从基本情况返回，n=0，fib(0(=0
从基本情况返回，n=1，fib(1(=1
递归情况返回，n=2，fib(2(=1
从缓存结果返回，n=1，fib(1(=1
从缓存结果返回，n=2，fib(2(=1
递归情况返回，n=3，fib(3(=2
递归情况返回，n=4，fib(4(=3
3
我知道，如果我使用字典来存储以前计算的结果，它将加快计算速度，并且不会重复计算。
但难道不应该有同样的9个函数调用用于动态编程吗；从缓存的结果返回"；(因为它们是经过计算的(，而不是只显示只剩下7个函数调用？
有没有遗漏什么，或者我没有正确编码？
请注意，动态编程方法可以防止递归的指数爆炸。
在递归方法中，要计算fib(4(，首先需要计算fib的(3(和(2(。
要计算fib(3(，您需要计算fib和fib(1(
现在在这个列表中，我们已经计算了两次fib(2(。
要计算fib(2(，我们需要fib(1(和fib(0(。
因此，最终，我们做出的决定是：纤维(4(fibfib(2(fib(1(fibfib(1(fib(0(
总共9个电话。
在动态方法中，要计算fib(4(，需要计算fib 3和fib 2。一旦我们计算了fib(3(，我们就不需要再次计算fib(2(，因为它已经在fib(三(期间计算过了。所以我们有：
你的呼叫是深度优先的，所以以下是呼叫方式：
fib(4(->fib(3(->fib(2(->fib(1(：基本情况，->fib(0(：基本情况
然后我们向上移动堆栈：fib(3(也调用fib(1(，但从基本情况返回。然后fib(4(也调用fib(2(，但从查找返回。
总共打了7个电话。