English Idiom in Unix: Directory Recursively

[Pascal J. Bourguignon]

Roland Hutchinson <my.spamtrap at verizon.net> writes:

> Sorry to have to contradict you, 

Don't be sorry.


> but it really is a textbook example of 
> recursion.  Try this psuedo-code on for size:  
>
> FUNCTION DIR-DELETE (directory)
>   FOR EACH entry IN directory
>   IF entry IS-A-DIRECTORY THEN DIR-DELETE (entry).	
>
> Well, now that's not just recursion; it's tail recursion.  

It's not tail recursion.  If you had indented your code properly, you'd
see why it's not:

    (defun dir-delete (directory)
      (loop for entry in directory
            do (if (is-a-directory entry)
                   (dir-delete entry))))

(I put parentheses, so my editor knows what I mean and can do the
indentation for me).


That's why walking a directory is done with a recursive procedure,
instead of an iterative one: it's much simplier.  To implement an
iterative procedure, you would have to manage a stack yourself, instead
of using the implicit stack of the recursive procedure.


> Tail recursion  can always be turned into an iteration when it is
> executed.  

All recursions can be turned into iterations, before execution.


> Reasonably  designed compilers are required to do so, in fact--have
> been for decades  now.  That doesn't mean that recursion isn't the
> best way of describing  the algorithm.



-- 
p__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.