使用动态规划实现斐波那契时的缓存命中次数疑问

先纠正你两个核心误解：

• 误解1：你认为调用fib(2)时fib(0)和fib(1)会命中，但实际上这两个是首次被调用，属于缓存未命中（miss），fib(2)本身也是首次调用，同样是miss。只有当同一参数的函数被第二次及以后调用时，才会产生缓存命中（hit）。
• 误解2：缓存容量maxsize=8没有影响命中次数，因为被淘汰的早期缓存条目（如fib(0)、fib(1)）在后续计算中不会被再次调用。

具体命中次数拆解 #

递归计算fib(30)是深度优先逻辑：

1. 从fib(30)开始，依次向下调用fib(29)、fib(28)……直到fib(0)，这些都是首次调用，共31次miss（对应fib(0)到fib(30)每个值各一次）。
2. 回溯计算阶段，每个fib(k)（k从1到28）会被第二次调用一次：
   • fib(1)被fib(3)第二次调用（hit）
   • fib(2)被fib(4)第二次调用（hit）
   • ……
   • fib(28)被fib(30)第二次调用（hit）
     这部分正好是28次hit，和你看到的结果完全匹配。

缓存容量的实际作用 #

maxsize=8会按LRU策略淘汰最近最少使用的缓存条目，但被淘汰的都是fib(0)、fib(1)这类早期值——它们在计算fib(m)（m≥3）时不会被再次调用，因为此时只需要fib(m-1)和fib(m-2)，这两个值是最近计算的，会被保留在缓存中直到不再被需要，因此不会影响命中次数。

内容的提问来源于stack exchange，提问作者user23359931