如何在Python中通过装饰器模式为递归算法实现记忆化？

编程语言 2026-07-10

我在学习 动态规划，并实现了一个递归算法来解决“爬楼梯”问题（本质上是在寻找第N 个斐波那契数）。

基本的递归版本对较小的输入还可以工作，但当 $N > 35$ 时，由于冗余计算，速度会变得极慢。我知道可以使用 记忆化 来优化它，但我想把算法的核心逻辑保持得“干净”，不把缓存逻辑与计算逻辑混在一起。

我做过的研究：

我发现 functools.lru_cache 在Python中存在，它能完美解决这个问题。
但出于教育目的，我想实现我自己的 装饰器（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） 原则？

能否展示从简单递归到装饰化实现的“正确”方式？

解决方案

你可以在装饰器函数内部定义这个字典。

下面是一个基本实现：

def memoize(fn):
    cache = {}
    def wrapper(*args):
        if args not in cache:
            cache[args] = fn(*args)
        return cache[args]
    return wrapper

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

为了处理关键字参数：

def memoize(fn):
    cache = {}
    delim = object()
    def wrapper(*args, **kwargs):
        key = *args, delim, *kwargs.items()
        if key not in cache:
            cache[key] = fn(*args, **kwargs)
        return cache[key]
    return wrapper

Python