[Python-Dev] Proper tail recursion

[Bob Ippolito]

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