用 Python 的 functools.lru_cache 给递归函数提速：一个真实的小案例

最近在做一个数据校验脚本时，我写了一个递归函数来计算某个配置项的“继承链深度”。逻辑不复杂，但数据量一上来，执行时间就从几百毫秒涨到了十几秒。排查后发现，问题出在大量重复的子问题计算上——典型的递归性能陷阱。

问题复现

简化后的代码如下：

def get_depth(config, key, cache=None):
    if key not in config:
        return 0
    parent = config[key].get("parent")
    if not parent:
        return 1
    return 1 + get_depth(config, parent)

配置结构类似：

config = {
    "a": {"parent": None},
    "b": {"parent": "a"},
    "c": {"parent": "b"},
    # ... 大量嵌套
}

当多个 key 共享同一条继承链时，get_depth 会反复计算相同的父节点深度。比如 c -> b -> a 和 d -> b -> a 中，b 和 a 的深度会被重复计算多次。

一行修复

Python 标准库的 functools.lru_cache 正好解决这类问题：

from functools import lru_cache

@lru_cache(maxsize=None)
def get_depth(config_key, config):
    ...

但 config 是 dict，不可哈希，不能直接作为缓存键。更实际的做法是把缓存放在函数内部，或者把 config 转成可哈希的元组。我这里选择了更轻量的方式——手动缓存：

def get_depth(config, key, _cache=None):
    if _cache is None:
        _cache = {}
    if key in _cache:
        return _cache[key]
    if key not in config:
        _cache[key] = 0
        return 0
    parent = config[key].get("parent")
    if not parent:
        _cache[key] = 1
        return 1
    depth = 1 + get_depth(config, parent, _cache)
    _cache[key] = depth
    return depth

调用时传入同一个 _cache 字典即可。实测在 5000 条配置、平均链长 8 的场景下，耗时从 12s 降到 0.08s。

几点经验

1. 递归 + 重复子问题 = 缓存候选。不是所有递归都需要缓存，但如果你发现同一个参数组合被反复调用，lru_cache 或手动 memo 几乎总是值得的。
2. 注意缓存键的可哈希性。lru_cache 要求所有参数可哈希，dict、list 都不行。必要时用 tuple(sorted(d.items())) 转换，或者像上面那样把缓存放在函数内部。
3. maxsize=None 要谨慎。无界缓存可能吃内存，生产环境建议设一个合理上限，比如 maxsize=1024。
4. 缓存不是银弹。如果递归本身有环（比如配置的 parent 指向自己），缓存救不了你，得先做环检测。

这个改动很小，但效果立竿见影。如果你的代码里也有类似的递归调用，不妨先 profile 一下，看看是不是重复计算在拖后腿。