[Python-Dev] Proper tail recursion (original) (raw)

Bob Ippolito 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, like Scheme, you have to have an explicit return to see any effect: def traverse(t, f): if t: f(t) traverse(t.left) 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.

-bob -------------- next part -------------- A non-text attachment was scrubbed... Name: smime.p7s Type: application/pkcs7-signature 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 mailing list