在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)

这可以通过其他答案显示的更简洁和Python来表达,而无需借助单独的辅助函数.但这显示了将非尾递归函数转换为尾递归函数的一般方法.

在上面,a称为累加器.一般的想法是将递归调用后通常执行的操作移动到下一个递归调用,通过包装工作外部调用已经完成"到目前为止"并在累加器中传递它.

如果map可以被认为是"调用f每个元素l,并返回结果列表" map_acc的意思,可以将其视为"调用f每个元素l,返回结果a列表,结果列表"公司生产的".