将递归函数转换为尾递归函数在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 的尾递归实现示例：

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 不支持 尾递归 的问题，这意味着每次函数调用时，调用栈都会一直保持在那儿。

Answer 2

这看起来是尾递归：

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

Answer 3

尾递归的意思是你必须直接返回递归调用的结果，而不进行其他操作。

在使用map函数时，明显的递归方式是对列表中的一个元素计算函数，然后用递归调用来处理剩下的列表。不过，你需要把处理一个元素的结果和处理剩下列表的结果结合起来，这就需要在递归调用之后再进行一些操作。

为了避免这种情况，一个很常见的做法是把组合操作放到递归调用里面；你把处理过的元素作为参数传入，让map负责进行组合。

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

这样就变成了尾递归！但这显然是错误的。在尾递归调用中，我们传入了三个参数，而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结合的结果列表，a是已经产生的结果列表”。