python之在python中将递归函数转换为尾递归函数

作为练习，我在 python 中使用递归实现了 map 函数，如下所示:

#map function that applies the function f on every element of list l and returns the new list  
def map(l,f): 
    if l == []: 
        return [] 
    else: 
        return [f(l[0])] + map(l[1:],f) 

我知道 python 不支持尾递归优化这一事实，但我将如何以尾递归方式编写相同的函数？

请帮忙 谢谢你

请您参考如下方法:

尾递归意味着您必须直接返回递归调用的结果，没有进一步的操作。

map 中明显的递归是在列表的一个元素上计算函数，然后使用递归调用来处理列表的其余部分。但是，您需要将处理一个元素的结果与处理列表其余部分的结果结合起来，这需要在递归调用之后进行操作。

避免这种情况的一种非常常见的模式是将组合移动到内部递归调用；您将处理过的元素作为参数传入，并使其成为 map 进行组合的职责的一部分。

def map(l, f): 
    if l == []: 
        return [] 
    else: 
        return map(l[1:], f, f(l[0])) 

现在是尾递归!但这也显然是错误的。在尾递归调用中，我们传递了 3 个参数，但 map 只接受两个参数。然后是我们如何处理第三个值的问题。在基本情况下(当列表为空时)，很明显:返回一个包含传入信息的列表。在递归情况下，我们正在计算一个新值，并且我们从顶部传入了这个额外参数，并且我们有递归调用。新值和额外的参数需要汇总在一起传递给递归调用，这样递归调用就可以尾递归了。所有这些都表明以下内容:

def map(l, f): 
    return map_acc(l, f, [])       
 
def map_acc(l, f, a): 
    if l == []: 
        return a 
    else: 
        b = a + [f(l[0])] 
        return map_acc(l[1:], f, b) 

如其他答案所示，可以更简洁地用 Python 方式表达，而无需求助于单独的辅助函数。但这显示了将非尾递归函数转换为尾递归函数的一般方法。

在上面，a 称为累加器。一般的想法是将递归调用之后通常执行的操作移动到下一个递归调用中，方法是结束外部调用“到目前为止”完成的工作并将其传递到累加器中。

如果 map 可以被认为是“对 l 的每个元素调用 f，并返回结果列表”， map_acc 可以被认为是指“在 l 的每个元素上调用 f，返回与 a< 组合的结果列表，已经生成的结果列表。