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

Question

作为练习，我在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不支持尾递归优化，但是我如何以尾递归方式编写相同的函数呢？

请帮帮忙谢谢

Answer 1

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

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)

正如其他答案所示，它可以更简洁和Pythonically地表达，而不需要求助于单独的助手函数。但这显示了将非尾递归函数转换为尾递归函数的一般方法。

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

如果map可以被认为意味着“在l的每个元素上调用f，并返回一个结果列表”，那么map_acc可以被认为意味着“在l的每个元素上调用f，返回一个与a结合的结果列表，一个已经生成的结果列表”。

Answer 2

这将是一个在尾递归中实现内置函数映射的示例：

def map(func, ls, res=None):
    if res is None:
        res = []
    if not ls:
        return res
    res.append(func(ls[0]))
    return map(func, ls[1:], res)

但它不会解决python不支持TRE的问题，这意味着每个函数调用的调用堆栈将始终保持不变。

Answer 3

这似乎是尾部递归的：

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

或者以更紧凑的形式：

def map(l,f,x=[]):
    return l and map(l[1:],f,x+[f(l[0])]) or x