python - 递归的中间结果

Question

我有一个问题，我需要生成一些自然递归计算的东西，但如果需要，我还需要能够询问递归中的中间步骤。

我知道我可以通过传递和改变列表或类似结构来做到这一点。然而，这对我来说看起来很难看，我确信一定有一种更简洁的方法，例如使用发电机。我理想中希望能够做的是:

intermediate_results = [f(x) for x in range(T)]
final_result = intermediate_results[T-1]

以有效的方式。虽然我的解决方案对性能并不关键，但我无法证明第一行中的大量冗余工作是合理的。在我看来，生成器非常适合这种情况，除了 f 从根本上来说更适合我的情况下的递归(至少在我看来，这与生成器完全相反，但也许我只是没有跳出框框思考得足够远)。

有没有一种简洁的 Pythonic 方式来做这样的事情，我只是不知道，或者我只需要投降并通过传递一个 来污染我的函数 f middle_results 列表，然后我将其作为副作用进行变异？

Answer 1

我有一个使用装饰器的通用解决方案。我们创建一个 Memoize 类，用于存储先前执行函数的结果(包括递归调用)。如果给定的参数已经被看到，则使用缓存的版本来快速查找结果。

自定义类比 lru_cache 具有优势，因为您可以看到结果。

from functools import wraps

class Memoize:
    def __init__(self):
        self.store = {}

    def save(self, fun):
        @wraps(fun)
        def wrapper(*args):
            if args not in self.store:
                self.store[args] = fun(*args)
            return self.store[args]
        return wrapper

m = Memoize()

@m.save
def fibo(n):
    if n <= 0: return 0
    elif n == 1: return 1
    else: return fibo(n-1) + fibo(n-2)

然后在运行不同的东西之后，您可以看到缓存包含的内容。当您运行 future 的函数调用时，m.store 将用作查找，因此不需要重做计算。

>>> f(8)
21
>>> m.store
{(1,): 1,
 (0,): 0,
 (2,): 1,
 (3,): 2,
 (4,): 3,
 (5,): 5,
 (6,): 8,
 (7,): 13,
 (8,): 21}

您可以修改 save 函数以使用函数名称和参数作为键，以便多个函数结果可以存储在同一个 Memoize 类中.