Q about tail recursion

[Tim Peters]

[Felix Thibault]
> 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

The "return add ..." is a tail call, yes.

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

Both "recur(recur, ..." and "container.append(..." are tail calls in this
"add").

> 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 ?

Perhaps you're missing that Python does no tail-call optimizations ever; or
perhaps that Python invents a "return None" for you if you don't code an
explict return yourself.

> 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 ?

Depending on your platform, time.time may have poor resolution; time.clock
is recommended for benchmarking (and, e.g., generally has better than
microsecond resolution under Windows).  The crap at the end of 1.70000004768
looks like floating-point roundoff error made visible.  If time.clock
doesn't have beeter resolution than time.time on your platform, you'll have
to arrange to capture the delta over a much longer stretch of time (e.g.,
call test.add in a loop and time the whole loop).

For the most part, you're timing how long it takes to do inlist[1:] (you
have a quadratic-time algorithm buried in here, first copying 999 elements,
then 998, then 997, etc).

after-all-this-i'm-still-not-sure-what-the-question-was<wink>-ly y'rs
    - tim