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

Josiah Carlson jcarlson at uci.edu
Fri Jul 16 09:52:07 CEST 2004

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.

If there were a practical method to remove recursion limits (seems like one is possible), that also preserved stack traces (seems like it can be done), with a method to set and get a synthetic recursion depth limit that gets checked before any call is made (seems like one already exists), and is set to a reasonable depth initally (like 1000), but can be set to None (no limit) by experienced users, then we would have the best of both worlds: a limit for mortals, no limit for experienced users. Heck, we could even require setting the recursion limit twice before it takes effect (those that want to use it must read the manual about how its use is discouraged).

Now, offering people enough rope to hang themselves with*, does not mean that it would be encouraged, and maybe allowing unlimited recursion with tracebacks should be a compile-time option (same internals, only one allows the recursion limit to be set, the other doesn't).

If unlimited recursion were allowed, perhaps limited tracebacks (first and last 500 stack frame traces), RLE tracebacks (though a clever programmer could easily destroy the generator with fewer than 64 functions, but we probably shouldn't do that), or combined limited and RLE tracebacks would be sufficient. What do I mean by an RLE traceback?

def f(n): ... if n > 1: ... f(n-1) ... f(1000) 'Traceback (most recent call last):' File "", line 1, in f 999x: File "", line 3, in f RuntimeError: maximum recursion depth exceeded def g(n): ... if n > 1: ... h(n) ... def h(n): ... if n > 1: ... g(n) ... g(1000) Traceback (most recent call last): File "", line 1, in ? 499x: File "", line 3, in g File "", line 3, in h File "", line 3, in g RuntimeError: maximum recursion depth exceeded #the following lines are a combination ... f(2000) 'Traceback (most recent call last):' File "", line 1, in f 499x: File "", line 3, in f 1000 levels of traceback clipped for your protection 500x: File "", line 3, in f RuntimeError: maximum recursion depth exceeded

Heck, the above would be nice even without unlimited recursion.

  1. giant tracebacks caused by running out of memory, being constructed in memory, causing annother out of memory error, which then causes a traceback to be printed while printing the traceback, which loses the real traceback
  2. giant tracebacks being printed to the logging module ...others I'm sure...

More information about the Python-Dev mailing list