[Python-Dev] Re: Proper tail recursion

[Josiah Carlson]

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


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


 - Josiah

*
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...