如何在Python中使用装饰器模式为递归算法正确添加记忆化——以爬楼梯问题为例

你的思路非常棒——既要保持核心计算逻辑的简洁，又想通过自己实现装饰器来理解底层原理，这是吃透Python闭包和装饰器模式的绝佳方式。你遇到的NameError和缓存重置问题，核心是没正确利用闭包来封装缓存的作用域，让我们一步步拆解解决：

为什么初始尝试会踩坑？ #

如果把缓存设为全局变量，确实能运行，但会有两个硬伤：

• 污染全局命名空间，其他代码可能误修改缓存
• 所有被装饰的函数会共享同一个缓存，不同递归函数的缓存会互相干扰

而如果把缓存放在装饰器的内层函数里，每次调用包装函数都会重新创建缓存，自然会导致缓存一次次重置。正确的做法是用闭包把缓存绑定到被装饰的函数实例上，让每个被装饰的函数拥有独立的私有缓存。

第一步：实现基础版@memoize装饰器 #

我们可以写一个两层结构的装饰器：外层函数负责创建并持有缓存字典，内层包装函数处理缓存逻辑和原函数调用：

def memoize(func):
    # 这个cache字典会被内层函数引用，形成闭包，不会被垃圾回收
    cache = {}
    
    def wrapper(n):
        # 先检查缓存中是否已有计算结果
        if n not in cache:
            # 无缓存则调用原函数计算，并存入缓存
            cache[n] = func(n)
        # 返回缓存结果
        return cache[n]
    
    # 返回包装后的函数
    return wrapper

第二步：将装饰器应用到爬楼梯函数 #

现在你可以直接用@memoize装饰你的count_stairs函数，核心递归逻辑完全不用修改：

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

# 测试n=35，现在瞬间出结果
print(count_stairs(35))  # 输出9227465

第三步：理解闭包的作用域魔法 #

这里的关键逻辑是：

• 当你用@memoize装饰count_stairs时，Python实际执行了count_stairs = memoize(count_stairs)
• memoize函数创建了cache字典，然后返回wrapper函数
• wrapper函数引用了外层的cache变量，这个变量不会随着memoize执行完毕而销毁——因为wrapper还持有对它的引用，这就是闭包的核心作用
• 每次递归调用count_stairs(n)，实际上调用的是wrapper(n)，它会复用同一个cache字典，彻底避免重复计算

第四步：优化装饰器支持通用参数 #

上面的基础版只支持单个位置参数，如果想让装饰器更通用（比如支持多个参数、关键字参数），可以修改成这样：

def memoize(func):
    cache = {}
    
    def wrapper(*args, **kwargs):
        # 把参数转换成可哈希的键（字典的键必须可哈希）
        key = (args, frozenset(kwargs.items()))
        if key not in cache:
            cache[key] = func(*args, **kwargs)
        return cache[key]
    
    return wrapper

这个版本可以适配大多数函数的参数情况，哪怕你的爬楼梯函数以后需要扩展参数，也能正常工作。

闭包方案对比全局变量的优势 #

用闭包封装缓存的好处很明显：

• 封装性：缓存属于被装饰函数私有，不会和其他函数的缓存冲突
• 无全局污染：不需要在全局命名空间定义缓存变量，避免命名冲突
• 可复用性：同一个装饰器可以安全装饰多个不同函数，每个函数都有独立缓存

现在你应该能理解functools.lru_cache的核心思路了——它本质就是一个更完善的memoize装饰器，支持缓存大小限制、参数类型检查等高级功能，但底层的闭包作用域原理和我们实现的版本完全一致。

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