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