我有一个问题，我需要生成自然递归计算的东西，但如果需要，我还需要能够询问递归中的中间步骤。
我知道我可以通过传递和更改列表或类似的结构来做到这一点。然而，这在我看来很难看，我相信一定有一种更整洁的方法，例如使用生成器。我最想做的事情是：
intermediate_results = [f(x) for x in range(T)]
final_result = intermediate_results[T-1]
以有效的方式。虽然我的解决方案不是性能关键型的，但我无法证明在第一行中的大量冗余工作是合理的。在我看来，生成器非常适合这一点，除了f从根本上更适合我的情况下的递归(至少在我看来这与生成器完全相反，但也许我只是没有跳出框框思考得足够远)。
有没有一种巧妙的Python方式来做我不知道的事情，或者我只需要屈服并通过传递一个intermediate_results列表来污染我的函数f，然后我将其作为副作用进行变异？
我有一个使用装饰器的通用解决方案。我们创建了一个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)
然后在运行不同的东西之后，您可以看到缓存中包含的内容。当您运行未来的函数调用时，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类中。
您可以使用现有的解决方案；冗余的"；调用f，但使用函数缓存将结果保存到以前对f的调用中。换句话说，当f(x1)被调用时，它的输入参数和相应的返回值被保存，下次调用时，结果只是从缓存中提取
有关此的标准库解决方案，请参阅functools.ru_cache
即：
from functools import lru_cache
@lru_cache
intermediate_results = [f(x) for x in range(T)]
final_result = intermediate_results[T-1]
然而，请注意，f必须是一个纯函数(没有副作用，1对1映射)，才能正常工作
考虑了您的意见后，我现在将尝试从另一个角度来看待这个问题。
因此，让我们考虑一个具体的例子：
def f(x):
a = 2
return g(x) + a if x != 0 else 0
def g(x):
b = 1
return h(x) - b
def h(x):
c = 1/2
return f(x-1)*(1+c)
我
首先，应该提到的是，(在我们的特定情况下)对于一些p，该算法的形式为：f(x) = p(f(x - 1))。由此得出CCD_ 11。这意味着我们只需要将p应用于0x次就可以得到所需的结果，这可以在迭代过程中完成，因此可以在不递归的情况下编写。尽管我相信你的真实情况要困难得多。此外，在这里停下来太无聊和没有信息了)
II
一般来说，我们可以将所有可能的解决方案分为两组：需要重构(即重写函数f、g、h)的解决方案和不需要重构的解决方案。后一个我几乎没有什么可以提供的(我认为没有人能提供)。然而，请考虑以下内容：
def fk(x, k):
a = 2
return k(gk(x, k) + a if x != 0 else 0)
def gk(x, k):
b = 1
return k(hk(x, k) - b)
def hk(x, k):
c = 1/2
return k(fk(x-1, k)*(1+c))
def printret(x):
print(x)
return x
f(4, printret) # see what happens
灵感来自连续传球风格，但事实并非如此。
有什么意义？这介于你传递一个列表来写下所有计算和记忆之间。这个k带有额外的行为，例如打印或写入列表(您可以创建一个写入某个列表的函数，为什么不呢？)。但如果你仔细观察，你会发现它几乎没有影响这些函数的内部代码(只有函数的输入和输出受到影响)，所以你可以产生一个与printret这样的函数相关的装饰器，它对f，g，h做基本上相同的事情。
- 优点：无需修改代码，比传递列表更灵活，无需额外工作(如记忆)
- 缺点：冲动(印刷或修改某物)，没有我们想要的那么灵活
III
现在，让我们看看修改函数体有什么帮助。不要害怕下面写的东西，慢慢来，玩一玩。
class Logger:
def __init__(self, lst, cur_val):
self.lst = lst
self.cur_val = cur_val
def bind(self, f):
res = f(self.cur_val)
return Logger([self.cur_val] + res.lst + self.lst, res.cur_val)
def __repr__(self):
return "Logger( " + repr({'value' : self.cur_val,'lst' : self.lst}) + " )"
def unit(x):
return Logger([], x)
# you can also play with lala
def lala(x):
if x <= 0:
return unit(1)
else:
return lala(x - 1).bind(lambda y: unit(2*y))
def f(x):
a = 2
if x == 0:
return unit(0)
else:
return g(x).bind(lambda y: unit(y + a))
def g(x):
b = 1
return h(x).bind(lambda y: unit(y - b))
def h(x):
c = 1/2
return f(x-1).bind(lambda y: unit(y*(1+c)))
f(4) # see for yourself
CCD_ 16被称为monad。我自己对这个概念不是很熟悉，但我想我做得很好)f，g，h是接受一个数字并返回Logger实例的函数。Logger的bind接受一个函数(如f)，并返回具有新值(由f计算)和更新的"日志"的Logger。在我看来，关键点是能够按照计算结果值的顺序，对收集的函数执行我们想要的任何操作。
后记
我根本不是函数式编程的"大师"，我相信我在这里错过了很多东西。但我所理解的是，函数式编程是关于反转程序的流程。这就是为什么，例如，我完全同意你关于生成器反对函数式编程的观点。当我们在函数func中使用生成器gen时，我们逐个生成到func的值，并且func在例如循环中对它们进行处理。函数方法是使gen成为以func为参数的函数，并使func对"已产生"的值进行计算。就像gen和func交换了位置。所以流量是反向的！还有很多其他的方法可以反转流量。君主就是其中之一。
itertools islice获取生成器、开始值和停止值。它将为您提供起始值和停止值之间的元素作为生成器。如果islice不清楚，你可以在这里查看文档https://docs.python.org/3/library/itertools.html
intermediate_result = map(f, range(T))
final_result = next(itertools.islice(intermediate_result, start=T-1, stop=T))