字典记忆化版本斐波那契数列的运行原理相关问题咨询

known = {0:0, 1:1}

def fibonacci(n):
    if n in known:
        return known[n]
    result = fibonacci(n-1) + fibonacci(n-2)
    known[n] = result
    return result

print(fibonacci(4))

运行流程（以fibonacci(4)调用为例） #

• 初始全局字典known仅存储了斐波那契数列的前两个基础值{0:0, 1:1}，调用fibonacci(4)时，首先判断4是否在known中，不存在则触发递归计算fibonacci(3) + fibonacci(2)
• 调用fibonacci(3)：3不在known中，触发计算fibonacci(2) + fibonacci(1)
• 调用fibonacci(2)：2不在known中，触发计算fibonacci(1) + fibonacci(0)
• fibonacci(1)和fibonacci(0)均命中known的存储值，分别返回1和0，加和得到1后，将键值对2:1存入known，返回结果1给上层调用
• 回到fibonacci(3)的计算逻辑：fibonacci(2)已经返回1，fibonacci(1)直接读known返回1，加和得到2后，将键值对3:2存入known，返回结果2给上层调用
• 回到fibonacci(4)的计算逻辑：fibonacci(3)返回2，fibonacci(2)直接读known返回1，加和得到3后，将键值对4:3存入known，返回结果3执行打印

运行速度快的原因说明 #

你观察到的速度优势不是因为Python本身提前存储了所有斐波那契数列结果，而是记忆化逻辑解决了普通递归的重复计算问题：

• 无优化的普通递归斐波那契，同一个n值会被重复计算非常多次，比如计算fib(4)时fib(2)会被算2次，计算fib(10)时fib(2)会被算21次，时间复杂度为指数级O(2ⁿ)，n越大运行效率越低
• 该记忆化版本中，每个n值只会在第一次调用时计算1次，计算完成后就会存入全局字典known，后续所有涉及该n值的调用都直接读字典返回结果，时间复杂度降到线性O(n)，所以运行速度会比普通递归快得多。如果后续再调用该函数计算更大的n值，之前已经存入known的结果都可以直接复用，不需要从头计算。

内容的提问来源于stack exchange，提问作者Gan-Od