On 2007-02-14, Gabriel Genellina <[EMAIL PROTECTED]> wrote:
> En Wed, 14 Feb 2007 03:09:37 -0300, [EMAIL PROTECTED]
><[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
