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

David Eppstein eppstein at ics.uci.edu
Mon Jul 19 20:30:30 CEST 2004

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

More information about the Python-Dev mailing list