might be of interest.

〈English Idiom in Unix: Directory Recursively〉
http://xahlee.org/comp/idiom_directory_recursively.html

------------------------------------------
English Idiom in Unix: Directory Recursively

Xah Lee, 2011-05-17

Today, let's discuss something in the category of lingustics.

You know how in unix tools, when you want to delete the whole
directory and all sub-directories and files in it, it's referred as
“recursive”?

For example, when you want to delete the whole dir in emacs, it
prompts this message: “Recursive delete of xx? (y or n) ”. (Note: to
be able to delete whole dir in emacs in dired, you'll first need to
turn it on. See: emacs dired tutorial.)

Here's another example. A quote from “rsync” man page:

     …
     This would recursively transfer all files from the directory …
     -r, --recursive             recurse into directories
     This tells rsync to copy directories recursively.  See also --
dirs (-d).
     …

Here's a quote from “cp”'s man page:

     -R, -r, --recursive
      copy directories recursively

and lots of other tools has a “-r” option, and they all refer to it as
“recursive”.

Though, if you think about it, it's not exactly a correct description.
“Recursive”, or “recursion”, refers to a particular type of algorithm,
or a implementation using that algorithm. Obviously, to process all
directory's content does not necessarily mean it must be done by a
recursive algorithm. A iteration can do it as well and it's easy to
have the full behavior and properties in the result as a recursive
approach, such as specifying depth order, level to dive into, etc.
(because, dir is a tree, and recursive algorithm is useful for walking
the tree data structure but is not necessary, because a tree can be
laid out flat. Any path order taken by a recursive approach can be
done by just enumerating the nodes in sequence. In fact, iteration
approach can be faster and simpler in many aspects. (i wrote a article
about this some 10 years ago, see: Trees and Indexes.) Note: this
thought about tree and its nodes as a set of node addresses can be
applied to any tree data structure, such as lisp's nested syntax, XML.
See: Programing Language: Fundamental Problems of Lisp.)

If you look at Windows or Mac OS X world, i don't think they ever
refer to dealing with whole dir as “recursive” in user interface. For
example, in Windows Vista, while changing properties of a folder, it
has this message:

        Apply changes to this folder only.
        Apply changes to this folder, subfolders and files.

Note the second choice. In unix, it would say “Apply changes to this
folder recursively.”

So, the word “recursive” used in unixes may be technically incorrect,
but more so, it's just not the right phrase. Because, we want to
communicate whether the whole content of a directory are processed,
not about certain algorithm or how it is implemented. A simple “all
the dir's branches/contents” or similar would be more apt.

Recently i was chatting in Second Life with someone (Sleeves). She's
typing, while i'm on voice. In part of our conversation, i said “you
sounded fine”. Note that it's technically incorrect, because she's
typing, not on voice. So she didn't actually make any “sound”. But to
say “you typed fine”, or “you chatted fine”, won't get the message
across.

That's idiom. When you interpret a idiom logically, it doesn't make
much sense, but people understand the particular phrase better anyway.
I suspect the “directory recursively” is also a idiom. It seems so
natural and really gets the point across, without any ill effects.
Even if the implementation actually used a iteration, it doesn't seems
to matter.

So the interesting question is, why this idiom works? Or, how it
developed?

I think, among programers (which all unix users are in the 1970s),
every one knows the concept of recursion, and many unix tools on dir
probably are implemented with a recursive algorithm. When you say “…
recursively”, the point gets across, because we all understand it,
even when we are not actually talking about implementation. The phrase
“… directory recursively” is short and memorable, while “… directory
and all its contents” or “… directory and all its branches” or “…
directory and all its sub-directories and files” are wordy and
unwieldy.
✍

    Idiocy Of Unix Copy Command
    Emacs Lisp Suggestion: Function to Copy/Delete a Directory
Recursively
    How to rsync, unison, wget, curl
    Hunspell Tutorial
    Mac OS X Resource Fork and Command Line Tips
    ImageMagick Tutorial
    Making System Calls in Perl and Python
    Unix And Literary Correlation
    The Unix Pestilence
    To An Or Not To An
    On “I” versus “i” (capitalization of first person pronoun)
    On the Postposition of Conjunction in Penultimate Position of a
Sequence
    What's Passive Voice? What's Aggressive Voice?
    Why You Should Avoid The Jargon “Tail Recursion”
    Why You should Not Use The Jargon Lisp1 and Lisp2
    Jargons of Info Tech Industry

 Xah

Xah Lee filted:

I suppose you've had a chance to read and absorb Knuth's 1974 paper "Structured
Programming with goto Statements"?...he establishes that it's possible to
convert *any* recursive algorithm into a corresponding iterative one....r

--
Me?  Sarcastic?
Yeah, right.

Sorry to have to contradict you, 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.  Tail recursion
can always be turned into an iteration when it is executed.  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.

The collocation in question is not "directory recursively"; it's
"delete ... recursively". Or "Change ...  recursively" (etc).  Does that
help?

It's also not an idiom.  It's meaning is completely determined by the
meaning of "delete" and the meaning of "recurse", as in "recurse down a
tree structure"--which is precisely what the various *nix commands do
when their recursive option is invoked.

"Recurse _down_ a tree" is an interesting phrase, though, as it implies
that, in computing, trees are thought of as growing with their root
topmost and their branches underneath -- i.e., upside-down!

I'm writing from alt.usage.english.  The non-natural language mavens may
have more to add.

--
Roland Hutchinson              

He calls himself "the Garden State's leading violist da gamba,"
... comparable to being ruler of an exceptionally small duchy.
--Newark (NJ) Star Ledger  ( http://tinyurl.com/RolandIsNJ )

Don't be sorry.

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.

All recursions can be turned into iterations, before execution.

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

On May 18, 9:51 am, Roland Hutchinson <my.spamt...@verizon.net> wrote:

Well and so far this thread is a textbook example of myths and
misconceptions regarding recursion :D

1. 'Recursive' is a meaningful adjective for algorithms only and not
data structures

2. Recursion is inefficient

which is a corollary to

3. Recursion is different from (more general, less efficient)
iteration

4. Recursion in 'recursion theory' aka 'computability theory' is
somehow different from recursion in programming.

Let me start with 1.

The Haskell (pseudocode) defn for lists is:
   data List(t) = []    |    (:) t List(t)

In words, a list over type t is either empty or is made byt taking a
(smaller) list and consing (:) and element onto it

It is only given this defn that al the list functions which are (in
the sense that
most programmers understand) recursive. For example:

len [] = 0
len (x:xs) = 1 + len xs

Note that the definition of List is primary and the recursive
functions on this definition are secondary to this definition.

What happens in languages more and more far from the 'functional
purity' of Haskell?
Much the same except that implementation details muddy the waters.

eg in C the defn for list (of an elsewhere specified type t) runs thus

struct node {
  t elem;
  struct node *next;

To make the recursion more explicit, introduce the typedef:

typedef struct node *nodeptr;

struct node {
  t elem;
  nodeptr next;

And we see clearly a mutual recursion in this data type:
node contains nodeptr
nodeptr points to node

So one could say that the C defn is more recursive than the Haskell
one in the sense that double recursion is 'more recursion' than
single.

I could continue down 2,3,4 but really it may be worthwhile if the
arguers first read the wikipedia disambiguation pages on recursion...

On May 18, 7:06 am, rusi <rustompm...@gmail.com> wrote:

No need - I have the Dictionary definition of recursion here:

Recursion: (N). See recursion.

On May 18, 11:50 am, Harrison Hill <harrish...@gmx.com> wrote:

Ha! Ha!

Worth also looking at the talk page of the recursive disambiguation
page:

http://en.wikipedia.org/wiki/Talk:Recursive

"Pascal J. Bourguignon" <p...@informatimago.com> writes:

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.

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

--
Thomas A. Russ,  USC/Information Sciences Institute

On Tue, 17 May 2011 15:26:42 -0700 (PDT), Xah Lee
:  If you look at Windows or Mac OS X world, i don't think they ever
:  refer to dealing with whole dir as “recursive” in user interface.

That's purely due to a difference in the level of abstraction.

Mac OS introduced its own vocabulary, of folders, where Unix and DOS
talked about directories.

A folder is a visual element on the screen; exactly modelling a paper
folder.  It goes without saying that if you bin a folder, the contents
goes with it.  Anything else would break the model and abstraction.

On Unix, the directory is just a file, listing other files by name
and disk location.  Then it is perfectly natural (although very
rarely smart) to delete a directory without any concequences to the
contents.  The data structure is clearly recursive; a file is either
an ordinary file or a directory, and a directory is a list of files.
An operation traversing the recursive data structure is recursive
regardless of how the algorithm is specified or implemented.

A large, although diminishing, fraction of Unix (excluding Mac OS)
users are likely to be familiar with the recursive structure of the
file system.

Now Mac OS X has maintained the folder concept of older mac generations,
and Windows has cloned it.  They do not want the user to understand
recursive data structures, and therefore, naturally, avoid the word.

--
:-- Hans Georg

Hans Georg Schaathun <h...@schaathun.net> writes:

Ironically, the only unix I know of where this makes a lot of sense is
Mac OS X (where multiple hard links to a single directory is utilised by
TimeMachine to minimise the size of incremental backup trees) :-)
--
  (espen)

["Followup-To:" header set to comp.lang.python.]
On 17 May 2011 23:42:20 -0700, Thomas A. Russ
:  Tree walks are the canonical example of what can't be done in an
:  iterative fashion without the addition of an explicitly managed stack

Of course you can do it.  It isn't nice, but it is possible.
I assume that you refer to depth first walks, as breadth first
is more easily described by iteration on a queue in the first place.

Depth first can be achieved by looping over the nodes, with a
state keeping references to the current and the previous node
considered.  By comparing the previous node (pointer or ID) to the
current node's parent and children one will know wherefrom the
current node was entered, and can choose the next child in the
list as the next node, or the parent if all children have been
visited.  A visit action may be added in any or all times the
node is visited.

This node requires no stack.  The only state space is constant,
regardless of the size of the tree, requiring just the two pointers
to previous and current.

--
:-- Hans Georg

Xah Lee <xah...@gmail.com>:

AFAICS what emacs calls "recursive delete" is what the ordinary person
would simply call "delete". Presumably the non-recursive delete is
called simply "delete" but is actually something more complicated than
delete, and you're supposed to know what that is.

Also (I'm speculating) a recursive delete means carrying out the
(ordinary, non-recursive) delete process on sub-directories,
recursively. The result of which is, put simply, to delete the
directory.

I find all this somewhat arcane. Questioning the precise suitability of
the word "recursive" seems like a quibble.

--
Mike Barnes
Cheshire, England

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.

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.

It's interesting to note that the definitions of 'recursive' to be found
in Wikipedia and Wiktionary have very little in common with the
definitions to be found in the dictionaries covered by Onelook.  No
wonder experts in different areas have trouble communicating with one
another.

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

On May 18, 5:09 pm, Peter Moylan <inva...@peter.pmoylan.org.invalid>
wrote:

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-...

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()

If you tell a joke, you have to tell it right.

Recursion: (N). See recursion. See also tail recursion.

Victor.
--
Victor Eijkhout -- eijkhout at tacc utexas edu

〈English Idiom in Unix: Directory Recursively〉
http://xahlee.org/comp/idiom_directory_recursively.html

that's good point. I think what happens is that the “recursive” has
become a idiom associated with directory to such a degree that the
unix people don't know what the fuck they are talking about. They just
simply use the word to go with directory whever they mean the whole
directory.

In the emacs case: “Recursive delete of xx? (y or n) ”, what could it
possibly mean by the word “recursive” there? Like, it might delete the
directory but not delete all files in it?

also, in the rsync case: “This would recursively transfer all files
from the directory … ”, what does the word “recursively” mean there?

 Xah

On 5/17/2011 3:26 PM, Xah Lee wrote:

     The proper terminology is "subtree", "subfolder", or "subdirectory".

                                        John Nagle

["Followup-To:" header set to comp.lang.python.]
On Wed, 18 May 2011 13:00:01 -0700 (PDT), Xah Lee
:  Mike Barnes <mikebar...@bluebottle.com> wrote:
: > I find all this somewhat arcane. Questioning the precise suitability of
: > the word "recursive" seems like a quibble.
:
:  that's good point. I think what happens is that the “recursive” has
:  become a idiom associated with directory to such a degree that the
:  unix people don't know what the fuck they are talking about. They just
:  simply use the word to go with directory whever they mean the whole
:  directory.

I totally agree that the motivation for the use of the word is
arcane.  We are many who understand and /need/ to understand
arcane aspects of the system.

However, the word «recursive» is not automatically associated
with discussion of directories.  Listing a directory, and
listing a directory recursively, are two different operations.
Both are useful and important, and the distinction is necessary.

:  In the emacs case: “Recursive delete of xx? (y or n) ”, what could it
:  possibly mean by the word “recursive” there? Like, it might delete the
:  directory but not delete all files in it?

Yes you /might/ do exactly that.  You just probably don't want to.
I agree that the question could be rephrased in a more userfriendly
manner, but OTOH, if you find the usage arcane, you probably don't
have any benefit from using emacs over less arcane editors either.

:  also, in the rsync case: “This would recursively transfer all files
:  from the directory … ”, what does the word “recursively” mean there?

Exactly the same as it does in «listing the directory recursively»
or «deleting the directory recursively».

Again the distinction could be useful.  A non-recursive «rsync dir1
dir2» probably isn't useful, but «rsync * dir2» might be.

--
:-- Hans Georg

On 05/18/2011 02:50 AM, Harrison Hill wrote:

The index of IBM's Document Composition Facility SCRIPT/VS Text
Programmer's Guide, Release 3.0 (form SH35-0069-2), put it thus:

Sadly, only the Release 4 manuals are available online anymore.

¬R

Xah Lee <xah...@gmail.com>:

My understanding is that non-recursive means, I think there are no (non-
empty?) subdirectories, or I haven't given the matter any thought, so if
there are any such subdirectories, tell me and don't do anything.
Recursive means I want everything deleted regardless. BICBW.

--
Mike Barnes
Cheshire, England

I believe the word "legend", or something equivalent, was used elsewhere
in this thread in this connection.  The supposed inefficiency of
recursive implementations is based largely on the properties of hardware
that is now obsolete.  With modern processors there's no great
efficiency hit.  In some of the smaller microcontrollers, it's true, you
do have to worry about stack overflow; but the ARM processors, for
example, provide plenty of stack space.

In the microcontroller world, the big performance hits come from the
fact that the only available compilers are for C and sometimes C++.
(And nobody uses assembly language except for the very little jobs.)
The nature of the C language prevents compilers from doing optimisations
that are standard in compilers for high-level languages.  Most C
compilers will, for example, always pass parameters on the stack,
despite the generous supply of registers available in newer hardware.

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

On 2011-05-18, Hans Georg Schaathun <h...@schaathun.net> wrote:

You imply they want to keep their users ignorant of these structures, as if
to keep something valuable from them. Wouldn't it be more honest, more to
the point and much simpler to state they don't NEED the user to understand
recursive - or indeed any other - data structures? And that the user doesn't
NEED to understand or know about them, just to use them?

After all they are users. They use their system for fun, learning or work.
Even a very competent or advanced use of a tool (computer, car, mobile phone,
fridge, TV, radio, toilet) in no way implies an understanding of it's inner
workings. Nor the need, nor the desire.

PS: Isn't this thread much ado about nothing?  :-)
It starts with the misconception (or should I say confusion?) between
performing a recursive job and using a recursive tool to do it. And then it
blazes off in these huge discusions about semantics to define a definition
of an abstraction of a alleady theoretical problem.

Glorious, just frelling glorious.    :-)
We have an expression for that. But I'll avoid using it, since it has the
word 'masturbation' in it...

And PPS: the P(P)S's don't specifically refer to your posting.

--
When in doubt, use brute force.
                -- Ken Thompson

You are right, of course.  Thanks for the correction.

My editor would have done that, too--if I had bothered to be thinking
clearly.

Got it!  Thanks again.

--
Roland Hutchinson              

He calls himself "the Garden State's leading violist da gamba,"
... comparable to being ruler of an exceptionally small duchy.
--Newark (NJ) Star Ledger  ( http://tinyurl.com/RolandIsNJ )

Very good!

--
Roland Hutchinson              

He calls himself "the Garden State's leading violist da gamba,"
... comparable to being ruler of an exceptionally small duchy.
--Newark (NJ) Star Ledger  ( http://tinyurl.com/RolandIsNJ )