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

David Eppstein eppstein at ics.uci.edu
Fri Jul 16 07:36:54 CEST 2004

In article <5.1.1.6.0.20040716000900.01e9bd40 at mail.telecommunity.com>, "Phillip J. Eby" <pje at telecommunity.com> wrote:

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. ;)

Where the recursion limit really bites me is the inability to do recursive depth first search on big graphs. Of course, I can simulate the stack myself and write the rest iteratively, but if I wanted to do that I'd go back to writing in assembly language.

-- David Eppstein http://www.ics.uci.edu/~eppstein/ Univ. of California, Irvine, School of Information & Computer Science

More information about the Python-Dev mailing list