English Idiom in Unix: Directory Recursively

[Thomas A. Russ]

Hans Georg Schaathun <hg at schaathun.net> writes:

> ["Followup-To:" header set to comp.lang.python.]
Ignored, since I don't follow that group.

> On Wed, 18 May 2011 20:20:01 +0200, Raymond Wiker
>   <raw at RAWMBP-2.local> wrote:
> :  	I don't think anybody mentioned *binary* trees. The context was
> :  directory traversal, in which case you would have nodes with an
> :  arbitrary (almost) number of children.
> 
> If we are being specific, then directory trees do have parent pointers.
> My point was really that «standard tree representations» is not a
> well-defined concept, and having parent pointers is as standard as
> not having them.

I suppose that I just assumed the standard mathematical definition of a
tree as a directed, acyclic graph.  It seems that in the context of
computability that one would tend toward using the mathematical
definitions.

Certainly in a complex graph with labeled links or trees with
backpointers, you would have an alternate data structure that you could
follow.

So, to be more precise, then:

  For directed, acyclic graphs without backpointers, you cannot write an
  iterative tree walker without simulating a stack.

The larger point is that there are algorithms that are inherently
recursive and for which there is no natural iterative algorithm.

-- 
Thomas A. Russ,  USC/Information Sciences Institute