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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4