Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: "Pascal J. Bourguignon" <pjb@informatimago.com>
Newsgroups: comp.lang.lisp,comp.lang.python,alt.usage.english
Subject: Re: English Idiom in Unix: Directory Recursively
Date: Wed, 18 May 2011 07:19:08 +0200
Organization: Informatimago
Lines: 49
Message-ID: <87aaekoab7.fsf@kuiper.lan.informatimago.com>
References: <c159267e-22f9-4821-a70d-2f111cc35de4@f31g2000pri.googlegroups.com> <iqvj9f$3ci$6@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: individual.net mVMKkxyLkIH5ZKDqDvfLHQZ7qfk26We/wwW0KP0epFgPKtms2L
Cancel-Lock: sha1:YmU1NzE5MzI5NTk3MDBjMjBlZjY0MjFkZGEwNWQyMTU1OGNjMWFkNQ== sha1:0EwXecxCoenJNGcY9gHPLo5KELc=
Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg==
X-Accept-Language: fr, es, en
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux)
Xref: x330-a1.tempe.blueboxinc.net comp.lang.lisp:3497 comp.lang.python:5651

Roland Hutchinson <my.spamtrap@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 {}.