Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!npeer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!news.glorb.com!usenet.stanford.edu!newsfeed.news.ucla.edu!news.usc.edu!news.isi.edu!usenet From: tar@sevak.isi.edu (Thomas A. Russ) Newsgroups: comp.lang.python,comp.lang.lisp Subject: Re: English Idiom in Unix: Directory Recursively Date: 19 May 2011 16:14:14 -0700 Organization: USC Information Sciences Institute Lines: 35 Sender: tar@blackcat.isi.edu Message-ID: References: <87aaekoab7.fsf@kuiper.lan.informatimago.com> NNTP-Posting-Host: blackcat.isi.edu Mime-Version: 1.0 Content-Type: text/plain; charset=latin-iso8859-1 Content-Transfer-Encoding: 8bit User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:5796 comp.lang.lisp:3559 Hans Georg Schaathun 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 > 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