算术运算符递归定义场景下如何实现记忆化/缓存功能？

问题根因 #

递归深度超限的核心原因有两点：

• 纯递归调用的栈深度随计算量级线性/指数级增长，超过Python默认的1000层递归栈限制
• 单纯增加记忆化装饰器只能减少重复参数的计算开销，无法降低单次计算的栈深度，因此单独使用达不到预期效果

可行优化方案 #

1. 记忆化装饰器优化 #

最初的Memoize类逻辑本身可用，但参数哈希逻辑可调整得更可靠，同时和蹦床函数结合时需要注意装饰器顺序：

class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args, **kwargs):
        # 用可哈希的参数元组作为key，比字符串拼接更可靠，无哈希冲突风险
        key = (args, tuple(sorted(kwargs.items())))
        if key not in self.memo:
            self.memo[key] = self.fn(*args, **kwargs)
        return self.memo[key]

2. 结合蹦床函数消除递归栈限制 #

蹦床函数是Python下最优的尾递归优化方向，原理是将递归调用转换为返回函数对象，用循环迭代执行替代栈调用，完全规避递归深度限制。装饰器使用时需要注意：记忆化装饰器要放在蹦床装饰器的外层，保证缓存的是最终计算结果，避免重复执行蹦床逻辑。

完整可运行优化代码 #

from typing import Callable

# 记忆化装饰器
class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args, **kwargs):
        key = (args, tuple(sorted(kwargs.items())))
        if key not in self.memo:
            self.memo[key] = self.fn(*args, **kwargs)
        return self.memo[key]

# 蹦床装饰器：消除递归栈限制
def trampoline(fn):
    def trampoline_inner(*args, **kwargs):
        res = fn(*args, **kwargs)
        while isinstance(res, Callable):
            res = res()
        return res
    return trampoline_inner

def successor(n):
    """返回n的后继数，所有运算的基础"""
    return n + 1

# 注意装饰器顺序：先套蹦床，再套记忆化
@Memoize
@trampoline
def _sum(n, m, cont=lambda x:x):
    return lambda: cont(n) if m == 0 else lambda: successor(_sum(n, m-1, lambda x: lambda: cont(x)))

@Memoize
@trampoline
def product(n, m, cont=lambda x:x):
    if m == 0:
        return lambda: cont(0)
    return lambda: cont(n) if m == 1 else lambda: _sum(product(n, m-1, lambda x: lambda: cont(x)), n)

@Memoize
@trampoline
def power(n, m, cont=lambda x:x):
    if m == 0:
        return lambda: cont(1)
    return lambda: cont(n) if m == 1 else lambda: product(power(n, m-1, lambda x: lambda: cont(x)), n)

@Memoize
@trampoline
def up_arrow_2(n, m, cont=lambda x:x):
    if m == 0:
        return lambda: cont(1)
    return lambda: cont(n) if m == 1 else lambda: power(up_arrow_2(n, m-1, lambda x: lambda: cont(x)), n)

@Memoize
@trampoline
def up_arrow_3(n, m, cont=lambda x:x):
    if m == 0:
        return lambda: cont(1)
    return lambda: cont(n) if m == 1 else lambda: up_arrow_2(up_arrow_3(n, m-1, lambda x: lambda: cont(x)), n)

# 测试
a = 2
b = 3
print(f"sum({a}, {b}) = {_sum(a,b)}")
print(f"product({a}, {b}) = {product(a,b)}")
print(f"power({a}, {b}) = {power(a,b)}")
print(f"up_arrow_2({a}, {b}) = {up_arrow_2(a,b)}")
print(f"up_arrow_3({a}, {b}) = {up_arrow_3(a,b)}")

补充说明 #

如果不需要保留递归的教学演示结构，也可以将所有递归逻辑改为迭代实现，同样可以规避递归深度问题，但会丧失原代码的教学直观性。

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