English Idiom in Unix: Directory Recursively

Hans Georg Schaathun hg at schaathun.net
Wed May 18 04:26:27 EDT 2011


["Followup-To:" header set to comp.lang.python.]
On 17 May 2011 23:42:20 -0700, Thomas A. Russ
  <tar at sevak.isi.edu> wrote:
:  Tree walks are the canonical example of what can't be done in an
:  iterative fashion without the addition of an explicitly managed stack

Of course you can do it.  It isn't nice, but it is possible.
I assume that you refer to depth first walks, as breadth first
is more easily described by iteration on a queue in the first place.

Depth first can be achieved by looping over the nodes, with a
state keeping references to the current and the previous node
considered.  By comparing the previous node (pointer or ID) to the
current node's parent and children one will know wherefrom the
current node was entered, and can choose the next child in the
list as the next node, or the parent if all children have been
visited.  A visit action may be added in any or all times the
node is visited.

This node requires no stack.  The only state space is constant,
regardless of the size of the tree, requiring just the two pointers
to previous and current.

-- 
:-- Hans Georg



More information about the Python-list mailing list