English Idiom in Unix: Directory Recursively

[rusi]

On May 18, 5:09 pm, Peter Moylan <inva... at peter.pmoylan.org.invalid>
wrote:
>
> 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.

Maybe the common usage mirrors the facts better than the lore that
half-baked programmers remain devoted to. Consider first
implementations:

The implementation of recursion by a typical language (eg gcc for C)
maximizes generality at the cost of efficiency

The implementation of a very special case -- tail recursion -- in some
special languages (most notably scheme) is required to be competitive
with the iterative solution.

[If I remember right in Chez scheme tail recursion was more efficient
than a do (iteration) because a do typically needed assignment and
assignment was more expensive than parameter passing]

But there is a wide spectrum of cases between the most general case of
recursion and tail recursion.

Some examples
1 A non-tail recursive function, with a single recursive call, when
implemented naively would push the return address.  This is
unnecessary as only a flag needs to be pushed -- return to internal
call point or return to external call point.  This itself can be
efficiently simulated by storing the recursion depth -- zero => jump
out; > 0 => jump to internal call

2. A single function with double recursion -- quicksort is the classic
-- can be implemented without recursion or stack.  It just needs a set
of pending begin-end pairs yet to be sorted.
This may look like the stack in another guise but unlike the stack it
does not need to store any function call return paraphernalia.

3. Tree recursion (though not the case of the OP) can be solved non-
recursively with threading
http://en.wikipedia.org/wiki/Threaded_binary_tree
and Schorr Waite Deutsch
http://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec21-schorr-waite.pdf

In fact the only example I can think of where the full blown
generality of recursion cannot be tightened is perhaps recursive
descent parsing.

So much for implementations.

Semantically the while loop

while B:
  statement

is equivalent to the recursion:

def stateiter():
  if B:
     statement
     stateiter()