本文目录导读：
- 📖 目录导读
- 为什么递归函数会“重复计算”？
- functools.lru_cache 是什么？原理简析
- 实战案例：斐波那契数列的优化对比
- lru_cache 的核心参数与适用场景
- 注意事项：缓存大小、不可哈希参数与性能陷阱
- 常见问题 FAQ（问与答）
- 总结：何时该用，何时不该用
📖 目录导读
- 为什么递归函数会“重复计算”？
- functools.lru_cache 是什么？原理简析
- 实战案例：斐波那契数列的优化对比
- lru_cache 的核心参数与适用场景
- 注意事项：缓存大小、不可哈希参数与性能陷阱
- 常见问题 FAQ（问与答）
- 何时该用，何时不该用
为什么递归函数会“重复计算”？
递归函数是许多算法（如树遍历、动态规划、分治）的核心实现方式，当递归调用涉及重叠子问题（Overlapping Subproblems） 时，重复计算会急剧膨胀。
以经典的斐波那契数列为例：
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
当我们计算 fib(5) 时，fib(3) 被计算了两次，而 fib(2) 被计算了三次。
随着 n 增大，时间复杂度呈指数级上升（O(2^n)），这种重复计算不仅浪费 CPU，还可能导致栈溢出。
核心问题： 一次函数调用会产生大量结构相同的子问题，但每次都要重新计算，而之前的结果没有被复用。
functools.lru_cache 是什么？原理简析
functools.lru_cache 是 Python 标准库中一个强大的装饰器（Decorator），它通过记忆化（Memoization） 技术，自动缓存函数的返回结果，当函数再次以相同的参数被调用时，直接从缓存中返回结果，而不是重新执行函数体。
工作原理：
- 内部维护一个基于字典的缓存，键由函数的参数组成。
- 采用 LRU（Least Recently Used，最近最少使用） 淘汰策略：当缓存大小达到上限时，自动移除最久未使用的缓存条目。
- 默认最大缓存大小为 128，你可以通过
maxsize参数自定义。
简单理解： 就像你有一张“结果备忘录”，每次遇到已经算过的问题，直接翻看备忘录，而不是重新算一遍。
实战案例：斐波那契数列的优化对比
1 未优化版本
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
import time
start = time.time()
print(fib(35)) # 约 9227465
print(f"耗时: {time.time()-start:.4f}s")
输出（典型值）：
9227465
耗时: 3.2140s2 使用 lru_cache 优化
from functools import lru_cache
@lru_cache(maxsize=None) # 无大小限制
def fib_cached(n):
if n <= 1:
return n
return fib_cached(n-1) + fib_cached(n-2)
start = time.time()
print(fib_cached(35))
print(f"耗时: {time.time()-start:.6f}s")
输出（典型值）：
9227465
耗时: 0.000020s对比结果：
- 从 3.21 秒降为 00002 秒，性能提升了约 16 万倍。
- 原因是
fib_cached(35)只需要计算 35 次不同的 n 值，而不是指数级调用。
lru_cache 的核心参数与适用场景
1 参数详解
| 参数 | 类型 | 说明 | 建议 |
|---|---|---|---|
maxsize |
int 或 None | 缓存可存储的最大结果数。None 表示无限制 |
对确定性函数（如纯计算）用 None；对内存敏感用 128 或 1024 |
typed |
bool | 若为 True，则不同类型的参数（如 1 和 1.0）视为不同键 | 默认 False，建议仅当需要区分类型时开启 |
2 适用场景
- ✅ 纯函数：输入相同，输出永远相同（无副作用）。
- ✅ 递归算法：动态规划、分治、回溯中的重复子问题。
- ✅ 高频调用的复杂计算：如解析配置文件、计算数学公式、生成重复的图形数据。
- ✅ 接口调用或数据库查询（配合缓存层）：但注意不要缓存动态数据。
3 不适合的场景
- ❌ 函数有副作用（如修改全局变量、写入文件、打印日志）。
- ❌ 参数是可变对象（如列表、字典）：它们不可哈希，无法作为缓存键。
- ❌ 参数组合无限且无规律：缓存会无限膨胀，失去 LRU 的意义。
注意事项：缓存大小、不可哈希参数与性能陷阱
1 缓存大小设置
@lru_cache(maxsize=32) # 仅缓存最近 32 次调用
def expensive_func(x):
# ...
maxsize太小，LRU 频繁淘汰，缓存命中率低，性能不升反降。maxsize太大或为None，内存占用可能飙升，建议先估算可能的参数数量。
2 不可哈希参数的处理
lru_cache 要求参数可哈希（Hashable），常见的不可哈希类型：
- 列表、集合、字典
- 自定义对象（除非实现了
__hash__）
解决方式：
将参数转换为可哈希形式，
@lru_cache
def process(tuple_of_list):
# 将列表转为元组
pass
3 性能陷阱
- 递归深度限制：
lru_cache不会消除递归深度，sys.setrecursionlimit仍需考虑。 - 装饰器顺序：如果同时使用多个装饰器，将
lru_cache放在最靠近函数定义的位置。 - 多线程安全：
lru_cache是线程安全的（内部使用了锁），但大量并发可能引起锁竞争。
常见问题 FAQ（问与答）
Q1：lru_cache 和手动用字典缓存有什么区别？
A：手动字典缓存需要自己管理键的生成、缓存的读取和更新，而 lru_cache 自动处理了 LRU 淘汰、线程安全、键的规范化和参数解包，代码更简洁，更不容易出错。
Q2：maxsize=None 会无限缓存，会不会导致内存泄漏？
A：不会立刻导致内存泄漏，但缓存会一直增长直到程序结束，如果函数的参数种类有限（如只有 100 种不同的输入），那就没问题，如果参数无限（如结合随机数），则应该设置 maxsize 或使用 LRU 淘汰策略。
Q3：我可以主动清除缓存吗？
A：可以。
- 清除单个缓存：
fib_cached.cache_clear() - 查看缓存信息：
fib_cached.cache_info()返回命中次数、未命中次数、最大大小、当前大小。
Q4：lru_cache 支持类方法或静态方法吗？
A：支持，但注意：如果装饰 类方法，self 会被视为一个参数，可能导致缓存命中率大幅下降（因为每个实例的 self 不同），建议对实例方法使用 lru_cache 时，设计为纯函数风格的类方法。
Q5：除了递归，还能用在哪些地方？
A：只要是确定性、重复调用、计算复杂的函数都可以。
- 解析大量相同格式的字符串
- 生成重复的加密哈希值
- 执行可重复的数学运算（如矩阵乘法）
何时该用，何时不该用
✅ 该用的情况
- 递归函数中存在重复子问题（概率极高）
- 纯计算函数,输入有限且可哈希
- 函数调用代价高（如复杂数学、IO 读配置文件）
- 需要快速原型优化,不想手动实现缓存
❌ 不该用的情况
- 函数内部修改了外部变量（副作用）
- 参数不可哈希,且无法轻易转换
- 函数仅在很少的场景下被调用（缓存带来的字典查找反而更慢）
- 参数组合完全随机（缓存几乎无法命中）
记住一个原则：不要过早优化，但要预判重复计算。 当你发现一个递归函数在 n=30 就开始卡顿时，functools.lru_cache 就是那个最优雅、最 Python 的解决方案。
本文参考了 Python 官方文档、Stack Overflow 讨论以及多个开源项目的实际使用案例，结合搜索引擎收录内容进行提炼与优化，希望你在实际开发中能灵活运用这一利器，让递归不再“重复”。