Geek asks and answers

Covering recursive tail recursive function in python

As an exercise, I implemented a 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 that python does not support tail recursion optimization, but how would I start writing the same function in tail recursive manner?

Please help. Thank you.

+1
source share
4 answers

Tail recursion means that you must directly return the result of a recursive call without further manipulation.

, , . , .

- ; map .

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

! . 3 , . , 3- . ( ), : , , . , , . , . :

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)

, , . .

a . , , , , , " ", .

map " f l ", map_acc " f on l, , a, , ".

+7

:

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, TRE, , .

0

:

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
0

, , - . , , "" foldr; foldl . , foldr , foldl -. , rev_map - "" (, ). , , ( , , , , , , ).

0

More articles:


All Articles