Coverting a recursive function to a tail recursive one in python

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)

I am aware of the fact that python does not support tail recursion optimization, but how wo开发者_如何学Gould i go about writing the same function in a tail recursive manner ?.

Please Help Thank You

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

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.

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

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)

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.

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.

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".

This will be an example of the implementation of the built-in function map in tail recursion:

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)

But it will not solve the problem of python not having support of TRE which mean that the call stack of each function call will be hold at all the time.

This seems to be tail recursive:

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

Or in more compact form:

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

not really an answer, sorry, but another way to implement map is to write it in terms of a fold. if you try, you'll find that it only comes out "right" with foldr; using foldl gives you a reversed list. unfortunately, foldr isn't tail recursive, while foldl is. this suggests that there's something more "natural" about rev_map (map that returns a reversed list). unfortunately i am not well enough educated to take this any further (i suspect you might be able to generalise this to say that there is no solution that doesn't use an accumulator, but i personally don't see how to make the argument).