Coverting递归函数的尾递归一个在Python

作为练习，我实现了使用递归的地图功能在python如下：Coverting递归函数的尾递归一个在Python

#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不支持尾递归优化，但我将如何去写尾部递归方式相同的功能？

请帮助谢谢

来源

2011-08-08 Joe

为什么这个函数不是尾递归？ –

它不是因为映射不是最后一个操作，映射的结果被添加到[f（l [0]）]，所以递归过程中的每个堆栈帧将需要 – Joe

好吧，所以你递归地生成元素，然后合并他们到一个列表。迭代过程会在每一步中更新列表的状态，并将其传递给下一次迭代，对吧？你需要更多的帮助吗？ –

这将是内置函数图中尾递归执行的例子：

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)

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

来源

2011-08-08 01:28:58 mouad

这似乎是尾递归：

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

来源

2011-08-08 01:29:23

使用一个可变的默认参数是不明智的想做：http：///stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument – mouad

@mouand，我知道这个功能。如果以正确的方式使用该功能，它不会导致任何错误。 –

除非你调用'my_list = map（empty_list，some_func）; my_list.append（5）'。现在每一个更多的空列表都将被映射到[5]。 – Ben

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

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

避免这种情况的一个很常见的模式是将组合内部的递归调用;你将处理后的元素作为参数传入，并使其成为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可以被认为是意为“叫f的l每一个元素，返回列表结果结合a，已经产生的结果列表“。

来源

2011-08-08 01:43:32 Ben

它可以，而不是键入另一个函数，使第三个参数的默认值作为参数在主函数中？第一次通话完成后会被修改。 –

@JuanGallostra是的，这是有效的（只要你小心不要改变或返回值可能会绑定到一些代码路径中的默认参数）。 – Ben

map_acc中的尾部调用应该是map_acc（l [1：]，f，b），因为map只需要2个参数。 – andrebask

不是一个真正的答案，对不起，但另一种实现地图的方法是把它写成一个折叠。如果你尝试，你会发现它只是出现在“正确”与foldr;使用foldl会给你一个反向列表。不幸的是，foldr不是尾递归，而foldl是。这表明关于rev_map有更多的“自然”（地图返回反向列表）。不幸的是，我没有受到足够的教育，无法进一步采取这一做法（我怀疑你可能会将此概括为说没有不使用累加器的解决方案，但我个人不知道如何提出论证）。

来源

2011-08-08 01:51:39

Coverting递归函数的尾递归一个在Python

回答

相关问题