[Python-Dev] Proper tail recursion

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