本文解析为何原递归斐波那契函数未能有效利用缓存，指出dict.get(key, default)中default参数被提前求值的根本原因，并提供手动缓存与标准库装饰器两种正确、高效的解决方案。
本文解析为何原递归斐波那契函数未能有效利用缓存，指出`dict.get(key, default)`中`default`参数被提前求值的根本原因，并提供手动缓存与标准库装饰器两种正确、高效的解决方案。
在实现带缓存的递归斐波那契函数时，一个常见误区是误用 dict.get(key, default) 的语义。例如以下代码看似“先查缓存、未命中再计算”，实则完全失效：
cache_mem = {}
def fib(n):
if n <= 1:
return n
else:
# ❌ 错误：fib(n-1) 和 fib(n-2) 总是会被执行！
cache_mem[n-1] = cache_mem.get(n-1, fib(n-1))
cache_mem[n-2] = cache_mem.get(n-2, fib(n-2))
return cache_mem[n-1] + cache_mem[n-2]问题根源在于 Python 的参数求值规则：所有函数调用的参数（包括 cache_mem.get(n-1, fib(n-1)) 中的 fib(n-1)）都会在 get() 方法执行前被无条件求值。这意味着即使 n-1 已存在于 cache_mem 中，fib(n-1) 仍会被递归调用，导致缓存形同虚设，时间复杂度仍为指数级 O(2ⁿ)。
✅ 正确做法是显式判断键是否存在，仅在未命中时触发递归计算：
cache_mem = {}
def fib(n):
if n <= 1:
return n
if n in cache_mem: # ✅ 显式检查，避免冗余调用
return cache_mem[n]
# 计算并缓存结果
cache_mem[n] = fib(n-1) + fib(n-2)
return cache_mem[n更进一步，推荐使用 Python 标准库提供的 functools.cache 装饰器——它自动处理缓存逻辑，线程安全，且支持 LRU 策略（可通过 @functools.lru_cache(maxsize=128) 自定义容量）：
from functools import cache
@cache
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
# 首次调用后，相同参数将直接返回缓存结果
print(fib(50)) # 毫秒级响应⚠️ 注意事项：
- 手动缓存需确保全局字典（如 cache_mem）作用域正确，避免多线程竞争（可改用 threading.Lock 或改用 @lru_cache）；
- @cache 要求函数参数必须是可哈希类型（int, str 等），不适用于含列表、字典等不可哈希参数的场景；
- 缓存本质是空间换时间，对深度递归需警惕栈溢出（Python 默认递归限制约 1000 层），必要时可结合迭代或尾递归优化。
通过理解参数求值时机并选择合适缓存机制，即可将斐波那契算法从指数复杂度降至线性 O(n)，真正发挥缓存的价值。
