[Python-Dev] Proper tail recursion

Phillip J. Eby pje at telecommunity.com
Fri Jul 16 06:13:46 CEST 2004


At 03:55 PM 7/16/04 +1200, Greg Ewing wrote:

>We could get the benefits of that just by eliminating recursive calls
>to ceval() when a Python function calls a Python function. I think
>that would be a worthwhile thing to do on its own, because it would
>mean recursion in pure Python would be limited only by available
>memory and not an arbitrary recursion limit, which has always seemed
>like a kludge to me.

Yeah, but it's a *useful* kludge to have a recursion limit.  Most 
algorithms that are "sensibly" recursive have some fan-out at each 
recursion level, such that the total recursion needed is something like 
log2N.  So as N grows, the relative amount of recursion shrinks.  A 
4-billion element binary tree traversal only needs 32 recursion levels.

So, realistically speaking, if you have hundreds of levels of recursion 
going on, you're probably doing something that should be expressed 
iteratively, or you're using 64-bit Python, in which case you probably have 
the stack space and CPU power to spare anyway.  ;)



More information about the Python-Dev mailing list