English Idiom in Unix: Directory Recursively

[Peter Moylan]

Thomas A. Russ wrote:
> "Pascal J. Bourguignon" <pjb at informatimago.com> writes:
> 
>> Roland Hutchinson <my.spamtrap at verizon.net> writes:
> 
>>> Tail recursion  can always be turned into an iteration when it is
>>> executed.  
>> All recursions can be turned into iterations, before execution.
> 
> True, but only by simulating the call stack in the iterative code.  To
> my mind that isn't really an iterative algorithm anymore if it ends up
> simulating the call stack.

When does a data structure stop being a simulation of a stack?  I've
often had to turn recursive algorithms into iterative ones, where the
solution turned out to be "simulating the call stack" only in a very
broad sense; a big stretch of the imagination is needed to see the
equivalent of push or pop operations.

> Tree walks are the canonical example of what can't be done in an
> iterative fashion without the addition of an explicitly managed stack

Let me throw in an example where the desired tree walk is neither
depth-first or breadth-first.  It's to do with the way I display my
family tree on my web site; an example may be found at
   http://www.pmoylan.org/cgi-bin/wft.cmd?D=moylan;P=I004
Most people familiar with algorithm design will, I believe, end up
deciding that the appropriate data structure in this case is a queue
rather than a stack.

ObAUE: In common parlance, the English word "recursion" means pretty
much the same as what computing people call "iteration".  This might be
the first time I have ever found a point of agreement with Xah Lee.

-- 
Peter Moylan, Newcastle, NSW, Australia.      http://www.pmoylan.org
For an e-mail address, see my web page.