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

Bob Ippolito bob at redivi.com
Thu Jul 15 18:02:41 CEST 2004

On Jul 15, 2004, at 11:40 AM, Christopher T King wrote:

On Thu, 15 Jul 2004, Bob Ippolito wrote:

On Jul 15, 2004, at 11:10 AM, Christopher T King wrote:

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. In Andrew's example, he noted that it would only help for list-like structures (i.e. those with mostly right nodes).

I think it's a misleading example nonetheless..

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. You're right -- even if Stackless doesn't do tail call optimization, implementation should be trivial. But there's no guarantee when or even if Stackless will be merged with CPython, and until that happens, Stackless isn't an option for many (most?) people.

Why not? Surely anyone who knows they want to do this kind of programming is capable of ./configure && make && sudo make install :)

Nearly all extension modules used with CPython should even be binary compatible with Stackless.

-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/a2cc4a50/smime.bin

More information about the Python-Dev mailing list