在python中将递归函数覆盖为尾递归函数 [英] Coverting a recursive function to a tail recursive one in python

问题描述

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

As an exercise, i implemented the map function using recursion in python as follows:

#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 不支持尾递归优化，但是我将如何以尾递归的方式编写相同的函数?.

I am aware of the fact that python does not support tail recursion optimization, but how would i go about writing the same function in a tail recursive manner ?.

请帮忙谢谢

推荐答案

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

Tail recursion means you must be directly returning the result of a recursive call, with no further manipulation.

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

The obvious recursion in map is to compute the function on one element of the list, then use a recursive call to process the rest of the list. However, you need to combine the result of processing one element with the result of processing the rest of the list, which requires an operation after the recursive call.

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

A very common pattern for avoiding that is to move the combination inside the recursive call; you pass in the processed element as an argument, and make it part of map's responsibility to do the combining as well.

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

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

Now it's tail recursive! But it's also obviously wrong. In the tail recursive call, we're passing 3 arguments, but map only takes two arguments. And then there's the question of what do we do with the 3rd value. In the base case (when the list is empty), it's obvious: return a list containing the information passed in. In the recursive case, we're computing a new value, and we have this extra parameter passed in from the top, and we have the recursive call. The new value and the extra parameter need to be rolled up together to be passed into the recursive call, so that the recursive call can be tail recursive. All of which suggests the following:

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 化地表达，而无需求助于单独的辅助函数.但这显示了将非尾递归函数转换为尾递归函数的一般方法.

Which can be expressed more concisely and Pythonically as other answers have shown, without resorting to a separate helper function. But this shows a general way of turning non-tail-recursive functions into tail recursive functions.

在上面，a 被称为累加器.总体思路是将您通常在递归调用之后执行的操作转移到下一个递归调用中，方法是将外部调用到目前为止"完成的工作打包起来，并将其传递到累加器中.

In the above, a is called an accumulator. The general idea is to move the operations you normally do after a recursive call into the next recursive call, by wrapping up the work outer calls have done "so far" and passing that on in an accumulator.

如果map可以理解为对l的每个元素调用f，并返回结果列表"，map_acc 可以被认为是在l的每个元素上调用f，返回一个与a<结合的结果列表/code>，已经产生的结果列表".

If map can be thought of as meaning "call f on every element of l, and return a list of the results", map_acc can be thought of as meaning "call f on every element of l, returning a list of the results combined with a, a list of results already produced".

这篇关于在python中将递归函数覆盖为尾递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！