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

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