Recursive calls and stack

[Neil Cerutti]

On 2007-02-14, Gabriel Genellina <gagsl-py at yahoo.com.ar> wrote:
> En Wed, 14 Feb 2007 03:09:37 -0300, jm.suresh at no.spam.gmail.com  
><jm.suresh at gmail.com> escribió:
>>  Is this way of implementation fill the stack space with the
>>  local variables inside each call. If this is not good, is
>>  there a better way to implement? Or python itself will
>>  understand that the calls happen in the last line, so local
>>  variables need not be pushed into the stack?
>
> I'm afraid not, the calls will be stacked until some object is
> found. Python does not do "tail recursion optimization" (at
> least, I'm not aware  of that).

To be just a little pedantic, it's "tail call optimization". Any
tail call can be optimized, not just recursive ones.

> But even if it could do that, in this case you have recursive
> calls between two functions, and that's a bit harder.

So the effect is that mutual recursion isn't actually any harder.

Moreover, if his functions calls really are tail-calls, then
translating them by hand into iteration might be fairly easy.

A simple, silly example:

def sum(seq):
  if len(seq) == 0:
    return 0
  else:
    return seq[0] + sum(seq[1:])

Above, sum is not a tail call, since the + operation must be
"defered" until after the call to sum returns.

Below, sum is a tail call.

def sum(seq, accum=0):
  if len(seq) == 0:
    return accum
  else:
    return sum(seq[1:], accum+s[0])

Since no state must be retained by sum when calling sum, it's a
tail call. The last version translates more or less directly into
a dumb while loop.

I don't believe Python does tail call optimization; at least it
isn't document that it does it.

-- 
Neil Cerutti
The audience is asked to remain seated until the end of the recession.
--Church Bulletin Blooper