如何在Python中自定义装饰器为递归算法实现记忆化优化？

阿华AIGC实验室

2026-6-1

问题描述

我正在学习Dynamic Programming（动态规划），已实现递归算法解决“爬楼梯”问题（本质是求第N个斐波那契数）。基础递归版本在小输入下可行，但因重复计算，当$N > 35$时速度极慢。我知道可通过**Memoization（记忆化）**优化，但希望保持算法核心逻辑“纯净”，不将缓存逻辑与计算逻辑混合。

已做调研

了解到Python中的functools.lru_cache可完美解决该问题；
但出于学习目的，我想自行实现Decorator（装饰器），理解背后的Architectural Pattern（架构模式）；
看过函数装饰器示例，但困惑如何在多次递归调用中处理memo字典的作用域。

当前实现（低效但纯净）

def count_stairs(n):
    # Base cases
    if n <= 1:
        return 1
    # Recursive step
    return count_stairs(n - 1) + count_stairs(n - 2)

# Problem: This takes several seconds for n=35
print(count_stairs(35))

目标

我想创建名为@memoize的装饰器，以便只需编写：

@memoize
def count_stairs(n):
    ...

遇到的问题

我尝试编写简单装饰器，但不断出现NameError，或缓存在每次调用时重置，因为不确定该将字典存储在哪里。缓存应该是全局变量，还是有办法将其封装在装饰器的闭包中以遵循更好的**Software Architecture（软件架构）**原则？

能否展示从简单递归到装饰器实现的正确架构转换方式？

解决方案

核心思路：用闭包封装缓存

最佳实践是把memo字典封装在装饰器的闭包中，既避免全局变量污染，又能让递归调用共享同一个缓存。装饰器本质是高阶函数，接收被装饰函数作为参数，返回带缓存逻辑的包装函数，同时将缓存绑定在闭包作用域内，不会被外部篡改。

步骤1：实现基础版`memoize`装饰器

def memoize(func):
    # 缓存字典属于闭包作用域，每个被装饰函数拥有独立缓存
    memo = {}
    def wrapper(n):
        # 检查当前参数是否已缓存
        if n not in memo:
            # 未缓存则调用原函数计算并存入缓存
            memo[n] = func(n)
        return memo[n]
    return wrapper

步骤2：装饰原递归函数

直接将装饰器应用到count_stairs上，核心逻辑无需修改：

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

# 现在n=100都能瞬间出结果
print(count_stairs(100))

作用域问题解析

使用@memoize装饰后，count_stairs会被替换为wrapper函数；
递归调用count_stairs(n-1)本质是调用wrapper(n-1)，而wrapper可访问外层闭包中的memo字典；
每个被@memoize装饰的函数都拥有独立的memo字典，不会与其他函数缓存冲突。

进阶：支持多参数的通用装饰器

上述版本仅支持单参数函数，若要提升通用性，可修改为接受任意参数：

def memoize(func):
    memo = {}
    def wrapper(*args, **kwargs):
        # 将参数转为可哈希的元组作为缓存键（字典键必须可哈希）
        key = (args, frozenset(kwargs.items()))
        if key not in memo:
            memo[key] = func(*args, **kwargs)
        return memo[key]
    return wrapper