[Python-Dev] Proper tail recursion
bob at redivi.com
Thu Jul 15 17:27:07 CEST 2004
On Jul 15, 2004, at 11:10 AM, Christopher T King wrote:
> On Thu, 15 Jul 2004, Andrew Koenig wrote:
>> [what I was trying to say, only better] :)
> Just a note: because Python sticks an implicit 'return None' at the
> end of
> a function, rather than returning the result of the last expression,
> Scheme, you have to have an explicit return to see any effect:
> def traverse(t, f):
> if t:
> return traverse(t.right)
But in this case what is tail-call optimization going to do for you?
You still require a stack at least the size of the height of your tree
because of traverse(t.left) since that can not be tail-call optimized
away, with the proposed algorithm.
I think Guido is in the right here, if you want to work around the
recursion limit, use Stackless.. It should already be able to go just
about as deep as you want.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 3589 bytes
Desc: not available
Url : http://mail.python.org/pipermail/python-dev/attachments/20040715/6cddbb9a/smime.bin
More information about the Python-Dev