[Python-Dev] Re: Proper tail recursion

[David Eppstein]

In article <005701c46db5$764b48d0$6602a8c0 at arkdesktop>,
 "Andrew Koenig" <ark-mlist at att.net> wrote:

> > I also haven't seen the use case that requires this and couldn't
> > easily be fixed by changing the data structure or code slightly.
> > (Andrew Koenig's theoretical objections don't count as use cases.)
> 
> Didn't we just hear that this problem affects pickling?

We heard that the recursion limit prevents recursive DFS from being 
applied to large graphs, and that pickling uses DFS.  However, tail 
recursion wouldn't help in this case -- it's a deep recursion but not a 
tail recursion.

I did end up implementing a non-recursive DFS, btw.  It has two 
advantages over recursive DFS: (1) the amount of stuff stored per stack 
item is much smaller: a pair (vertex, iterator of neighbors), rather 
than all the overhead of a call stack frame, and (2) the flat control 
structure allows it to be used as a simple generator (e.g. for listing 
vertices in preorder or postorder).  The disadvantage is that the code 
is (I think) less readable than a recursive DFS would be.  You can view 
my attempt at http://www.ics.uci.edu/~eppstein/PADS/DFS.py (one hint 
that Python's control structures are missing something is the explicit 
use of try...iterator.next()...except StopIteration) but please send any 
feedback about my code to me off-list since it's not really a python-dev 
issue any more.

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