函数组合与装饰器：递归斐波那契记忆化实现的问题探究

我正在练习用记忆化（memoization）优化递归函数，于是编写了如下记忆化斐波那契生成器：

memo = {}
def memo_fibo(n):
    if n not in memo:
        if n < 2:
            memo[n] = n
        else:
            memo[n] = memo_fibo(n - 2) + memo_fibo(n - 1)
    return memo[n]

这段代码运行良好！接下来我想将记忆化逻辑通用化，编写一个能为其他函数添加记忆化功能的函数，于是写出如下代码：

def memoize(f):
    cache = {}
    def memoized(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]
    return memoized

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

mf = memoize(fibo)

但这段代码无法正常工作，尽管我只是进行了简单的函数嵌套。更奇怪的是，使用装饰器写法：

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

却能正常运行。这是为什么？为什么简单的函数组合无法得到正确结果，与装饰器写法存在差异？是我的函数组合语法有误，还是memoize函数的实现不适用于函数组合？我对装饰器的理解还不够深入，若能明白如何让这两种写法等价，将极大帮助我掌握装饰器。

核心问题出在递归函数内部的函数引用上：

• 执行 mf = memoize(fibo) 时，memoized 里调用的 f(x) 是原始未记忆化的 fibo，而原始 fibo 内部递归调用的是它自己（无缓存版本），所以整个递归过程完全没用到缓存，和原始 fibo 效率一样，根本没实现记忆化效果。
• 装饰器写法 @memoize 本质是把装饰后的函数重新赋值给了原函数名 fibo。也就是说，装饰后 fibo 指向的是带缓存的 memoized 函数，原始 fibo 内部的递归调用现在会指向这个缓存版本，每一步递归都走缓存逻辑，自然能正常工作。

要让函数组合写法和装饰器等价，只需把装饰后的函数重新赋值给原始函数名，就像装饰器自动做的那样：

def memoize(f):
    cache = {}
    def memoized(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]
    return memoized

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

# 关键操作：覆盖原始函数名，让递归调用指向缓存版本
fibo = memoize(fibo)
# 现在调用fibo即可使用记忆化功能
print(fibo(10))

另外，你的 memoize 仅支持单参数函数，若要适配多参数场景，可以把缓存键改成包含 *args 和 **kwargs 的元组：

def memoize(f):
    cache = {}
    def memoized(*args, **kwargs):
        # 用不可变类型作为缓存键
        key = (args, frozenset(kwargs.items()))
        if key not in cache:
            cache[key] = f(*args, **kwargs)
        return cache[key]
    return memoized

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