[Python-Dev] Re: Proper tail recursion

[David Eppstein]

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