如何用 Python 装饰器为递归算法添加 Memoization？

2026-11-04数据小陈

可以把缓存字典放在 memoize 内部、wrapper 外部。装饰函数时创建字典，后续调用通过闭包访问同一个字典，无需使用全局变量。题目中的 count_stairs 定义在模块级，递归调用时会找到装饰后的包装函数，因此每一层递归都能查询缓存。

可直接使用的实现

下面的装饰器适用于接收一个可哈希参数的函数。爬楼梯问题中的 n 应为非负整数，示例没有额外添加输入校验。

from functools import wraps


def memoize(func):
    cache = {}

    @wraps(func)
    def wrapper(n):
        if n not in cache:
            cache[n] = func(n)
        return cache[n]

    return wrapper


@memoize
def count_stairs(n):
    if n <= 1:
        return 1
    return count_stairs(n - 1) + count_stairs(n - 2)


print(count_stairs(5))   # 8
print(count_stairs(35))  # 14930352

@wraps(func) 用于保留原函数的名称、文档字符串等元信息，缓存逻辑本身不依赖它。

缓存为什么不会在递归时重置？

cache = {} 在调用 memoize(func) 时执行，而不是在每次调用 wrapper(n) 时执行。

函数定义及其装饰器执行后，返回的 wrapper 持有对 cache 的引用。只要这个包装函数仍然可达，缓存就可以继续保留。一次顶层调用结束后，缓存不会自动清空，下次调用同一个装饰后的函数时仍可复用。

如果把字典放进包装函数内部，每次调用都会创建一个空缓存：

def memoize(func):
    @wraps(func)
    def wrapper(n):
        cache = {}  # 每次调用都会重新创建，无法跨调用复用
        if n not in cache:
            cache[n] = func(n)
        return cache[n]

    return wrapper

正确实现中的 cache[n] = ... 修改的是字典内容，没有重新绑定 cache 变量，因此不需要 global 或 nonlocal。

每次调用 memoize 都会创建一个新字典，所以不同函数分别应用 @memoize 时，各自拥有独立缓存。

递归调用为什么也会经过装饰器？

对于这里的写法：

@memoize
def count_stairs(n):
    if n <= 1:
        return 1
    return count_stairs(n - 1) + count_stairs(n - 2)

可以将装饰过程理解为：

def count_stairs(n):
    if n <= 1:
        return 1
    return count_stairs(n - 1) + count_stairs(n - 2)


count_stairs = memoize(count_stairs)

重新赋值后，模块中的 count_stairs 指向 wrapper，而 wrapper 闭包中的 func 仍然指向原始函数。

调用过程如下：

调用 count_stairs(n)，进入 wrapper(n)。
如果缓存中已有结果，直接返回。
如果没有结果，调用原始函数 func(n)。
原始函数执行递归表达式时，再次查找名称 count_stairs，找到的是包装函数。
子问题计算完成后，包装函数保存并返回结果。

例如，计算 count_stairs(5) 时，较早的递归分支会求出并缓存部分子问题，后续分支遇到相同参数时就能直接取值。

这里的递归调用使用了已绑定到包装函数的名称。如果函数通过其他引用直接调用原始函数，就可能绕过缓存。

出现 NameError 时检查什么？

没有具体异常信息，无法确定原先尝试中的错误位置。可以先检查以下几点：

memoize 必须在使用 @memoize 之前定义。
cache 必须位于 wrapper 能访问的作用域内。
装饰器必须返回 wrapper，而不是提前调用 wrapper()。
缓存未命中时应调用保存的原函数 func(n)；若在包装函数中再次调用自身，会造成无休止的递归。

还要确认缩进正确。原始材料中的代码缺少函数体和条件分支的缩进，直接执行会先遇到缩进错误。

优化效果与适用范围

普通递归会反复计算相同的子问题，调用数量随 n 指数增长。加入缓存后，对于非负整数输入，从 0 到 n 的各个状态最多求解一次，因此状态求值次数为 O(n)，缓存最多保存 O(n) 项，递归深度仍为 O(n)。这里按状态数量分析，没有计入大整数运算及存储成本随数值增长的变化。

使用时还要注意：

输入范围：当前算法假定 n 为非负整数。n <= 1 这个条件本身也会接受负数，但这不代表负数具有合理的爬楼梯含义。
函数形式：示例装饰器只处理一个参数。扩展到多个位置参数和关键字参数时，需要另外设计缓存键。
缓存正确性：该装饰器适合结果由参数决定的计算。如果函数依赖可变外部状态、时间或随机数，复用旧结果可能不符合预期。
内存与递归：示例没有缓存容量限制或清理接口，也不会消除 Python 的递归深度限制。较大输入可以考虑迭代实现。
并发行为：示例没有提供线程同步，也不保证并发调用同一个参数时只计算一次。

按常见的 F(0) = 0、F(1) = 1 定义，这段爬楼梯代码计算的是 F(n + 1)，而不是 F(n)，因为它使用了 count_stairs(0) = count_stairs(1) = 1 的初始条件。