Q about tail recursion

Felix Thibault felixt at dicksonstreet.com
Sat Feb 26 08:37:55 CET 2000


I was following the funtional programming thread and trying to get an idea
about what tail recursion was, so I made these two functions:

def add(inlist, sofar=0):
    if inlist:
        return add(inlist[1:], sofar+inlist[0])
    else:
        return 0

def faketailadd(inlist):
    sum = []
    def add(recur,inlist, sofar, container):
        if inlist:
            recur(recur, inlist[1:], sofar+inlist[0], container)
        else:
            container.append(sofar)
    add(add, inlist, 0, sum)
    return sum[0]

and tested them, and got:

>>> a=time.time();b=test.add(k1);time.time()-a
1.70000004768
>>> a=time.time();b=test.faketailadd(k1);time.time()-a
1.70000004768

(k1 is range(1000))

Does this mean that even though there are no return's in faketailadd's
add, the function still has to work its way back up from all those
recursive calls ? Or something like that ? Or does it just mean I
misunderstood what tail-call optimizing is like? Or does that too-
good-to-be-true less-than-1-nanosecond difference mean my testing
is flawed ? 

dys-functionally y'rs,

Felix





More information about the Python-list mailing list