FAQ
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

Search Discussions

  • Ian Kelly at May 17, 2011 at 11:20 pm

    On Tue, May 17, 2011 at 4:26 PM, Xah Lee wrote:
    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.
    Only when used as programming jargon. In mathematics, "recursive
    function" does *not* mean "a function implemented using a recursive
    algorithm". It's just a formal definition of a specific class of
    mathematical functions.

    As it turns out, "recursive" also has a non-technical definition,
    which again has nothing to do with algorithms except in the broadest
    sense:

    recursive adj.
    1. pertaining to or using a rule or procedure that can be applied repeatedly
    (from dictionary.com)

    This definition fits the Unix usage perfectly.
  • Chris Angelico at May 17, 2011 at 11:42 pm

    On Wed, May 18, 2011 at 8:26 AM, Xah Lee wrote:
    ? ? ?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.?
    I think this is more about the Windows and Mac philosophy to dumb
    things down at the expense of verbosity, than about Unix jargon.
    Archiving and compressing files using Phil Katz's PKZip utility uses
    the -r option to include all subdirectories; it's documented as
    "recurse subudirectories", which makes plenty of sense. (There's an
    equivalent utility from Info-ZIP in a lot of Linux distros, and it has
    the same option, listed as "recurse into directories".) Can you think
    of any other single word that clearly describes the action of tracing
    into all subdirectories? Even if it's not algorithmically accurate, it
    carries the meaning. The "mind-space" requirement is quite compact;
    you can ignore the "into subdirectories" part and just think "-r means
    recurse", whereas the alternative is "-r means files in this directory
    and all its subdirectories".

    Chris Angelico
  • Steven W. Orr at May 18, 2011 at 1:16 am

    On 5/17/2011 6:26 PM, Xah Lee wrote:
    might be of interest.

    ?English Idiom in Unix: Directory Recursively?
    http://xahlee.org/comp/idiom_directory_recursively.html
    The answer is from compute science 101. From any standard data structures
    course, you learn the algorithm for how to walk a tree. To make it simple, the
    example is to use a binary tree which means that any non-leaf node of a tree may
    only have two child nodes, which are designated as Left and Right. There are
    only three things that are possible: Visit, Go Left, or Go Right. This means
    that a tree traversal program can only be written three ways:
    A PreOrder Traversal will Visit, Go Left, Go Right.
    An InOrder Traversal will Go Left, Visit, Go Right.
    A PostOrder Traversal will Go Left, Go Right, Visit.

    So, the Visit function is the function that does whatever you want to have
    happen at that node. Selection of whether you want to do things like copy, print
    or delete are designated by what kind of traversal you perform. And, since the
    Traversal function calls itself, it is, by definition, recursive.

    QED.

    --
    Time flies like the wind. Fruit flies like a banana. Stranger things have .0.
    happened but none stranger than this. Does your driver's license say Organ ..0
    Donor?Black holes are where God divided by zero. Listen to me! We are all- 000
    individuals! What if this weren't a hypothetical question?
    steveo at syslang.net
  • Roland Hutchinson at May 18, 2011 at 4:51 am

    On Tue, 17 May 2011 15:26:42 -0700, Xah Lee wrote:

    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.
    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.
    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.
    The collocation in question is not "directory recursively"; it's
    "delete ... recursively". Or "Change ... recursively" (etc). Does that
    help?
    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?
    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 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
    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 )
  • Pascal J. Bourguignon at May 18, 2011 at 5:19 am

    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 {}.
  • Thomas A. Russ at May 18, 2011 at 6:42 am

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

    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
  • Hans Georg Schaathun at May 18, 2011 at 8:26 am
    ["Followup-To:" header set to comp.lang.python.]
    On 17 May 2011 23:42:20 -0700, Thomas A. Russ
    wrote:
    : 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
  • Thomas A. Russ at May 18, 2011 at 4:16 pm

    Hans Georg Schaathun <hg at schaathun.net> writes:

    ["Followup-To:" header set to comp.lang.python.]
    On 17 May 2011 23:42:20 -0700, Thomas A. Russ
    wrote:
    : 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.
    Well, unless you have a tree with backpointers, you have to keep the
    entire parent chain of nodes visited. Otherwise, you won't be able to
    find the parent node when you need to backtrack. A standard tree
    representation has only directional links.

    Consider:

    A--+---B----+---D
    +---E
    +---F
    +---C

    If all you keep is the current and previous node, then the only thing
    you have reference do when doing the depth-first traverse is:
    1. Current = A, Previous = null
    2. Current = B. Previous = A
    3. Current = D Previous = B
    4. Current = E Previous = D
    5. now what? You can't get from E or D back to B.
    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.
    This will only work if there is a backpointer to the parent.

    So you have to add one extra pointer for each node back to its parent.
    This extra pointer will be the size of the graph, rather than (on
    average) log of the size of the graph stack frames.


    --
    Thomas A. Russ, USC/Information Sciences Institute
  • Hans Georg Schaathun at May 18, 2011 at 6:11 pm
    ["Followup-To:" header set to comp.lang.python.]
    On 18 May 2011 09:16:26 -0700, Thomas A. Russ
    wrote:
    : Well, unless you have a tree with backpointers, you have to keep the
    : entire parent chain of nodes visited. Otherwise, you won't be able to
    : find the parent node when you need to backtrack. A standard tree
    : representation has only directional links.

    The array representation of a binary tree is standard, and the
    ?back? (parent) pointers are mathematically given. /Some/
    standard tree representation do not have parent pointers.

    You are right that I assumed parent pointers of some description;
    but it does demonstrate that tree walks can be done iteratively,
    without keeping a stack of any sort.


    --
    :-- Hans Georg
  • Raymond Wiker at May 18, 2011 at 6:20 pm

    Hans Georg Schaathun <hg at schaathun.net> writes:

    ["Followup-To:" header set to comp.lang.python.]
    On 18 May 2011 09:16:26 -0700, Thomas A. Russ
    wrote:
    : Well, unless you have a tree with backpointers, you have to keep the
    : entire parent chain of nodes visited. Otherwise, you won't be able to
    : find the parent node when you need to backtrack. A standard tree
    : representation has only directional links.

    The array representation of a binary tree is standard, and the
    ?back? (parent) pointers are mathematically given. /Some/
    standard tree representation do not have parent pointers.
    I don't think anybody mentioned *binary* trees. The context was
    directory traversal, in which case you would have nodes with an
    arbitrary (almost) number of children.
    You are right that I assumed parent pointers of some description;
    but it does demonstrate that tree walks can be done iteratively,
    without keeping a stack of any sort.
    Except that the chain of parent pointers *would* constitue a
    stack.
  • Hans Georg Schaathun at May 18, 2011 at 6:39 pm
    ["Followup-To:" header set to comp.lang.python.]
    On Wed, 18 May 2011 20:20:01 +0200, Raymond Wiker
    wrote:
    : I don't think anybody mentioned *binary* trees. The context was
    : directory traversal, in which case you would have nodes with an
    : arbitrary (almost) number of children.

    If we are being specific, then directory trees do have parent pointers.
    My point was really that ?standard tree representations? is not a
    well-defined concept, and having parent pointers is as standard as
    not having them.

    : Except that the chain of parent pointers *would* constitue a
    : stack.

    In the sense that the tree itself is a stack, yes. But if we
    consider the tree (or one of its branches) to be a stack, then
    the original claim becomes a tautology.

    But you do have a point. Keeping a stack of nodes on the path
    back to root is a great deal simpler and cheaper than a call
    stack, and not really a significant expense in context.


    --
    :-- Hans Georg
  • Raymond Wiker at May 18, 2011 at 7:09 pm

    Hans Georg Schaathun <hg at schaathun.net> writes:

    ["Followup-To:" header set to comp.lang.python.]
    On Wed, 18 May 2011 20:20:01 +0200, Raymond Wiker
    wrote:
    : I don't think anybody mentioned *binary* trees. The context was
    : directory traversal, in which case you would have nodes with an
    : arbitrary (almost) number of children.

    If we are being specific, then directory trees do have parent pointers.
    My point was really that ?standard tree representations? is not a
    well-defined concept, and having parent pointers is as standard as
    not having them.
    I cannot see that going back to the original case (directory
    traversal) is any more specific than talking about a completely
    unrelated case (binary trees).

    Further, even though most(?) hierarchical file systems have parent
    pointers, this is not necessary.
    : Except that the chain of parent pointers *would* constitue a
    : stack.

    In the sense that the tree itself is a stack, yes. But if we
    consider the tree (or one of its branches) to be a stack, then
    the original claim becomes a tautology.
    No, the tree is not a stack, but the chain of parent pointers
    from a particular node may be considered as a stack that records the
    path taken to reach the current node.
    But you do have a point. Keeping a stack of nodes on the path
    back to root is a great deal simpler and cheaper than a call
    stack, and not really a significant expense in context.
    For this particular operation, possibly. For other tree
    operations, a single parent pointer may not be sufficient.
  • Hans Georg Schaathun at May 18, 2011 at 8:02 pm
    ["Followup-To:" header set to comp.lang.python.]
    On Wed, 18 May 2011 21:09:15 +0200, Raymond Wiker
    wrote:
    : > In the sense that the tree itself is a stack, yes. But if we
    : > consider the tree (or one of its branches) to be a stack, then
    : > the original claim becomes a tautology.
    :
    : No, the tree is not a stack, but the chain of parent pointers
    : from a particular node may be considered as a stack that records the
    : path taken to reach the current node.

    That is one of its branches, yes, path from root towards leaf.
    It is part of the data structure, and you don't travers a data
    structure without using the datastructure.

    : > But you do have a point. Keeping a stack of nodes on the path
    : > back to root is a great deal simpler and cheaper than a call
    : > stack, and not really a significant expense in context.
    :
    : For this particular operation, possibly. For other tree
    : operations, a single parent pointer may not be sufficient.

    Que? What tree operations do you have in mind? We have covered
    all the standard textbook tree walks by now.

    --
    :-- Hans Georg
  • Raymond Wiker at May 18, 2011 at 8:40 pm

    Hans Georg Schaathun <hg at schaathun.net> writes:

    ["Followup-To:" header set to comp.lang.python.]
    On Wed, 18 May 2011 21:09:15 +0200, Raymond Wiker
    wrote:
    : > In the sense that the tree itself is a stack, yes. But if we
    : > consider the tree (or one of its branches) to be a stack, then
    : > the original claim becomes a tautology.
    :
    : No, the tree is not a stack, but the chain of parent pointers
    : from a particular node may be considered as a stack that records the
    : path taken to reach the current node.

    That is one of its branches, yes, path from root towards leaf.
    It is part of the data structure, and you don't travers a data
    structure without using the datastructure.

    : > But you do have a point. Keeping a stack of nodes on the path
    : > back to root is a great deal simpler and cheaper than a call
    : > stack, and not really a significant expense in context.
    :
    : For this particular operation, possibly. For other tree
    : operations, a single parent pointer may not be sufficient.

    Que? What tree operations do you have in mind? We have covered
    all the standard textbook tree walks by now.
    I said tree operations, not tree walks. A tree operation might
    involve several tree walks. Further, there has been an implicit
    assumption (I think) in this discussion that the order of children is
    given, or does not matter - if this is not the case, then you also need
    to maintain a stack of data structures representing lists (or sets) of
    children.
  • Hans Georg Schaathun at May 19, 2011 at 4:56 am
    ["Followup-To:" header set to comp.lang.python.]
    On Wed, 18 May 2011 22:40:28 +0200, Raymond Wiker
    wrote:
    : I said tree operations, not tree walks. A tree operation might
    : involve several tree walks.

    OK. The original claim under dispute regarded tree walks.

    : Further, there has been an implicit
    : assumption (I think) in this discussion that the order of children is
    : given, or does not matter - if this is not the case, then you also need
    : to maintain a stack of data structures representing lists (or sets) of
    : children.

    It assumes that there is some canonical ordering on the children. If
    the tree nodes store their children as sets, where the implementation
    does not guarantee that they can be retrieved in the same order every
    time, then it breaks. However, that would be an unusual implementation.
    The tree has to store the children for each node, one way or another.
    The only thing I am assuming is that the children can be inspected in
    the same order every time the node is visited.


    --
    :-- Hans Georg
  • Thomas A. Russ at May 19, 2011 at 11:14 pm

    Hans Georg Schaathun <hg at schaathun.net> writes:

    ["Followup-To:" header set to comp.lang.python.]
    Ignored, since I don't follow that group.
    On Wed, 18 May 2011 20:20:01 +0200, Raymond Wiker
    wrote:
    : I don't think anybody mentioned *binary* trees. The context was
    : directory traversal, in which case you would have nodes with an
    : arbitrary (almost) number of children.

    If we are being specific, then directory trees do have parent pointers.
    My point was really that ?standard tree representations? is not a
    well-defined concept, and having parent pointers is as standard as
    not having them.
    I suppose that I just assumed the standard mathematical definition of a
    tree as a directed, acyclic graph. It seems that in the context of
    computability that one would tend toward using the mathematical
    definitions.

    Certainly in a complex graph with labeled links or trees with
    backpointers, you would have an alternate data structure that you could
    follow.

    So, to be more precise, then:

    For directed, acyclic graphs without backpointers, you cannot write an
    iterative tree walker without simulating a stack.

    The larger point is that there are algorithms that are inherently
    recursive and for which there is no natural iterative algorithm.

    --
    Thomas A. Russ, USC/Information Sciences Institute
  • Chris Angelico at May 18, 2011 at 6:41 pm

    On Thu, May 19, 2011 at 4:20 AM, Raymond Wiker wrote:
    You are right that I assumed parent pointers of some description;
    but it does demonstrate that tree walks can be done iteratively,
    without keeping a stack of any sort.
    ? ? ? ?Except that the chain of parent pointers *would* constitue a
    stack.
    Howso? It's part of your data structure, not part of your algorithm;
    and it's not something that grows and shrinks as you traverse. These
    considerations may be crucial if, for instance, you want to walk your
    tree in a signal handler, and you don't know how much memory is
    available to you...

    Chris Angelico
  • Chris Angelico at May 18, 2011 at 6:12 pm

    On Thu, May 19, 2011 at 2:16 AM, Thomas A. Russ wrote:
    Well, unless you have a tree with backpointers, you have to keep the
    entire parent chain of nodes visited. ?Otherwise, you won't be able to
    find the parent node when you need to backtrack. ?A standard tree
    representation has only directional links.
    Sure, but there are plenty of trees that do have parent pointers.
    Widgets on every system I've tinkered with always have, and in a
    directory structure that doesn't allow files to be in multiple places,
    it's not hard (look at the . and .. entries in a directory). Of
    course, file systems are not idealized tree structures, so things will
    be a bit more complicated.

    ChrisA
  • Pascal J. Bourguignon at May 18, 2011 at 6:57 pm

    tar at sevak.isi.edu (Thomas A. Russ) writes:

    Well, unless you have a tree with backpointers, you have to keep the
    entire parent chain of nodes visited. Otherwise, you won't be able to
    find the parent node when you need to backtrack. A standard tree
    representation has only directional links.

    Consider:

    A--+---B----+---D
    +---E
    +---F
    +---C

    If all you keep is the current and previous node, then the only thing
    you have reference do when doing the depth-first traverse is:
    1. Current = A, Previous = null
    2. Current = B. Previous = A
    3. Current = D Previous = B
    4. Current = E Previous = D
    5. now what? You can't get from E or D back to B.
    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.
    This will only work if there is a backpointer to the parent.
    No, you don't need backpointers; some cases have been mentionned in the
    other answer, but in general:

    (defun parent (tree node)
    (if (member node (children tree))
    tree
    (some (lambda (child) (parent child node)) (children tree))))

    Yes, the question wasn't about time complexity.

    --
    __Pascal Bourguignon__ http://www.informatimago.com/
    A bad day in () is better than a good day in {}.
  • Thomas A. Russ at May 19, 2011 at 11:17 pm

    "Pascal J. Bourguignon" <pjb at informatimago.com> writes:

    tar at sevak.isi.edu (Thomas A. Russ) writes:
    This will only work if there is a backpointer to the parent.
    No, you don't need backpointers; some cases have been mentionned in the
    other answer, but in general:

    (defun parent (tree node)
    (if (member node (children tree))
    tree
    (some (lambda (child) (parent child node)) (children tree))))

    Yes, the question wasn't about time complexity.
    :-p

    Um, this is a recursive function. Inside PARENT, there is another call
    to PARENT.

    --
    Thomas A. Russ, USC/Information Sciences Institute
  • Pascal J. Bourguignon at May 20, 2011 at 12:38 am

    tar at sevak.isi.edu (Thomas A. Russ) writes:

    "Pascal J. Bourguignon" <pjb at informatimago.com> writes:
    tar at sevak.isi.edu (Thomas A. Russ) writes:
    This will only work if there is a backpointer to the parent.
    No, you don't need backpointers; some cases have been mentionned in the
    other answer, but in general:

    (defun parent (tree node)
    (if (member node (children tree))
    tree
    (some (lambda (child) (parent child node)) (children tree))))

    Yes, the question wasn't about time complexity.
    :-p

    Um, this is a recursive function. Inside PARENT, there is another call
    to PARENT.
    Feel free to derecursive it.

    --
    __Pascal Bourguignon__ http://www.informatimago.com/
    A bad day in () is better than a good day in {}.
  • Antti J Ylikoski at May 20, 2011 at 9:00 am

    On 20.5.2011 3:38, Pascal J. Bourguignon wrote:
    tar at sevak.isi.edu (Thomas A. Russ) writes:
    "Pascal J. Bourguignon"<pjb at informatimago.com> writes:
    tar at sevak.isi.edu (Thomas A. Russ) writes:
    This will only work if there is a backpointer to the parent.
    No, you don't need backpointers; some cases have been mentionned in the
    other answer, but in general:

    (defun parent (tree node)
    (if (member node (children tree))
    tree
    (some (lambda (child) (parent child node)) (children tree))))

    Yes, the question wasn't about time complexity.
    :-p

    Um, this is a recursive function. Inside PARENT, there is another call
    to PARENT.
    Feel free to derecursive it.
    In the general case, to derecursive a function necessitates programming
    a stack, among other things.............

    Antti "Andy" Ylikoski
  • Peter Moylan at May 18, 2011 at 12:09 pm

    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.
  • Rusi at May 18, 2011 at 1:14 pm

    On May 18, 5:09?pm, Peter Moylan 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()
  • Peter Moylan at May 19, 2011 at 1:06 am

    rusi wrote:
    On May 18, 5:09 pm, Peter Moylan 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]
    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.
  • Jonathan de Boyne Pollard at May 21, 2011 at 8:32 am

    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.
    However, some C compilers will *also* have one or more "go faster"
    calling conventions that pass parameters in registers, which can be
    employed. Over in the PC world, such "go faster" calling conventions
    are even the default calling convention if no calling convention is
    explicitly specified, for some C and C++ compilers.


    http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Compiler

    http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Optlink

    http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Watcall
  • Lars Enderin at May 21, 2011 at 9:52 am

    2011-05-21 10:32, Jonathan de Boyne Pollard skrev:
    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.
    However, some C compilers will *also* have one or more "go faster"
    calling conventions that pass parameters in registers, which can be
    employed. Over in the PC world, such "go faster" calling conventions
    are even the default calling convention if no calling convention is
    explicitly specified, for some C and C++ compilers.


    http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Compiler


    http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Optlink


    http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Watcall
    Please include attributions, in this case for Peter Moylan and rusi!
  • Lars Enderin at May 21, 2011 at 9:54 am
    2011-05-21 11:52, Lars Enderin skrev:
    Please include attributions, in this case for Peter Moylan and rusi!
    Just Peter Moylan, sorry!
  • Lars Enderin at May 21, 2011 at 9:56 am

    2011-05-21 11:54, Lars Enderin skrev:
    2011-05-21 11:52, Lars Enderin skrev:
    Please include attributions, in this case for Peter Moylan and rusi!
    Just Peter Moylan, sorry!
    Ignore the above.
  • Grant Edwards at May 21, 2011 at 3:34 pm

    On 2011-05-19, Peter Moylan wrote:

    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.
    I've been doing microcontroller stuff for 25+ years, almost all in C,
    and I don't think I've never seen such a compiler. Even on the
    register-starved 6800 architecture, the first parameter was passed in
    a register. On architectures with more registers (H8, MSP430, ARM,
    etc.) It's usually the first 3 or so parameters that are found in
    registers.

    --
    Grant Edwards grant.b.edwards Yow! Gee, I feel kind of
    at LIGHT in the head now,
    gmail.com knowing I can't make my
    satellite dish PAYMENTS!
  • Roland Hutchinson at May 20, 2011 at 6:50 am

    On Wed, 18 May 2011 07:19:08 +0200, Pascal J. Bourguignon wrote:

    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))))
    You are right, of course. Thanks for the correction.
    (I put parentheses, so my editor knows what I mean and can do the
    indentation for me).
    My editor would have done that, too--if I had bothered to be thinking
    clearly.
    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.
    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 )
  • Rusi at May 18, 2011 at 6:06 am

    On May 18, 9:51?am, Roland Hutchinson wrote:

    Sorry to have to contradict you, but it really is a textbook example of
    recursion. ?Try this psuedo-code on for size: ?
    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...
  • Harrison Hill at May 18, 2011 at 6:50 am

    On May 18, 7:06?am, rusi wrote:
    On May 18, 9:51?am, Roland Hutchinson wrote:

    Sorry to have to contradict you, but it really is a textbook example of
    recursion. ?Try this psuedo-code on for size: ?
    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...
    No need - I have the Dictionary definition of recursion here:

    Recursion: (N). See recursion.
  • Rusi at May 18, 2011 at 7:16 am

    On May 18, 11:50?am, Harrison Hill wrote:
    Rusi wrote
    I could continue down 2,3,4 but really it may be worthwhile if the
    arguers first read the wikipedia disambiguation pages on recursion...
    No need - I have the Dictionary definition of recursion here:

    Recursion: (N). See recursion.
    Ha! Ha!

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

    http://en.wikipedia.org/wiki/Talk:Recursive
  • Peter Moylan at May 18, 2011 at 12:19 pm

    Harrison Hill wrote:
    On May 18, 7:06 am, rusi wrote:

    I could continue down 2,3,4 but really it may be worthwhile if the
    arguers first read the wikipedia disambiguation pages on recursion...
    No need - I have the Dictionary definition of recursion here:

    Recursion: (N). See recursion.
    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.
  • Rantingrick at May 29, 2011 at 8:16 pm

    On May 18, 7:19?am, Peter Moylan wrote:

    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.
    Yes, and when you extrapolate that conclusion into the current hodge
    podge of natural languages you begin to understand the genesis of
    human beings selfish nature.
  • Peter Moylan at May 30, 2011 at 12:58 pm

    rantingrick wrote:
    On May 18, 7:19 am, Peter Moylan wrote:

    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.
    Yes, and when you extrapolate that conclusion into the current hodge
    podge of natural languages you begin to understand the genesis of
    human beings selfish nature.
    I do?

    --
    Peter Moylan, Newcastle, NSW, Australia. http://www.pmoylan.org
    For an e-mail address, see my web page.
  • Victor Eijkhout at May 18, 2011 at 5:59 pm

    Harrison Hill wrote:

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

    Recursion: (N). See recursion.
    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
  • Roland Hutchinson at May 20, 2011 at 6:54 am

    On Wed, 18 May 2011 12:59:45 -0500, Victor Eijkhout wrote:

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

    Recursion: (N). See recursion.
    If you tell a joke, you have to tell it right.

    Recursion: (N). See recursion. See also tail recursion.
    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 )
  • Chris Angelico at May 20, 2011 at 7:10 am

    On Wed, 18 May 2011 12:59:45 -0500, Victor Eijkhout wrote:
    Recursion: (N). See recursion. See also tail recursion.
    caching proxy (n): If you already know what recursion is, this is the
    same. Otherwise, see recursion.

    ChrisA
  • Rantingrick at May 29, 2011 at 8:28 pm

    On May 18, 12:59?pm, s... at sig.for.address (Victor Eijkhout) wrote:
    Harrison Hill wrote:
    No need - I have the Dictionary definition of recursion here:
    Recursion: (N). See recursion.
    If you tell a joke, you have to tell it right.
    Jeez, speaking of bad colloquialisms...

    """if you're going to "share" a joke you should at least "recite" it
    CORRECTLY."""

    Thank you.
  • Peter Moylan at May 30, 2011 at 1:02 pm

    rantingrick wrote:
    On May 18, 12:59 pm, s... at sig.for.address (Victor Eijkhout) wrote:
    Harrison Hill wrote:
    No need - I have the Dictionary definition of recursion here:
    Recursion: (N). See recursion.
    If you tell a joke, you have to tell it right.
    Jeez, speaking of bad colloquialisms...

    """if you're going to "share" a joke you should at least "recite" it
    CORRECTLY."""
    He was her man
    But he was doing her incorrectly.

    I'm not convinced that this new meaning of "share" has contributed
    anything of value to the language. Which is possibly why people stopped
    using it in about the 1980s.

    --
    Peter Moylan, Newcastle, NSW, Australia. http://www.pmoylan.org
    For an e-mail address, see my web page.
  • Rantingrick at May 29, 2011 at 8:28 pm

    On May 18, 12:59?pm, s... at sig.for.address (Victor Eijkhout) wrote:
    Harrison Hill wrote:
    No need - I have the Dictionary definition of recursion here:
    Recursion: (N). See recursion.
    If you tell a joke, you have to tell it right.
    Jeez, speaking of bad colloquialisms...

    """if you're going to "share" a joke you should at least "recite" it
    CORRECTLY."""

    Thank you.
  • Glenn Knickerbocker at May 18, 2011 at 8:54 pm

    On 05/18/2011 02:50 AM, Harrison Hill wrote:
    Recursion: (N). See recursion.
    The index of IBM's Document Composition Facility SCRIPT/VS Text
    Programmer's Guide, Release 3.0 (form SH35-0069-2), put it thus:
    Circular definition
    See definition, circular
    definition
    circular 211
    See also circular definition
    Sadly, only the Release 4 manuals are available online anymore.

    ?R
  • Ian Kelly at May 18, 2011 at 6:58 am

    On Wed, May 18, 2011 at 12:06 AM, rusi wrote:
    4. Recursion in 'recursion theory' aka 'computability theory' is
    somehow different from recursion in programming.
    Um, it is. Consider the simple function (lambda x, y: x + y).
    Mathematically, this function is recursive. Algorithmically, it is
    not. Do you disagree?
  • Rusi at May 18, 2011 at 7:10 am

    On May 18, 11:58?am, Ian Kelly wrote:
    On Wed, May 18, 2011 at 12:06 AM, rusi wrote:
    4. Recursion in 'recursion theory' aka 'computability theory' is
    somehow different from recursion in programming.
    Um, it is. ?Consider the simple function (lambda x, y: x + y).
    Mathematically, this function is recursive. ?Algorithmically, it is
    not. ?Do you disagree?
    See the definition of primitive recursion eg.

    http://en.wikipedia.org/wiki/Primitive_recursive_function#Definition

    (2 of the second set of "more complex" definitions) from where the
    name 'primitive recursion' is presumably derived)

    And for the more general (wider) class of 'recursive' functions (in
    the math sense aka computable functions) see a little below:

    http://en.wikipedia.org/wiki/Primitive_recursive_function#Relationship_to_recursive_functions

    Of course I grant that the adjective 'recursive' is used differently
    in computability and in programming but the roots are not all that
    different.

    If I remember right (I may be misremembering) Hofstader, referring to
    the invention of 'recursive function' by Godel, says something to the
    effect that Godel was inventing lisp 30 years before lisp...
  • Ian Kelly at May 18, 2011 at 2:32 pm

    On Wed, May 18, 2011 at 1:10 AM, rusi wrote:
    Um, it is. ?Consider the simple function (lambda x, y: x + y).
    Mathematically, this function is recursive. ?Algorithmically, it is
    not. ?Do you disagree?
    See the definition of primitive recursion eg.

    http://en.wikipedia.org/wiki/Primitive_recursive_function#Definition

    (2 of the second set of "more complex" definitions) from where the
    name 'primitive recursion' is presumably derived)

    And for the more general (wider) class of 'recursive' functions (in
    the math sense aka computable functions) see a little below:

    http://en.wikipedia.org/wiki/Primitive_recursive_function#Relationship_to_recursive_functions
    I know what primitive recursive and computable functions are, thanks.
    What you're failing to explain is why you would consider that function
    to be recursive from a programming standpoint. In programming, when
    we say a function is recursive, we mean that it is implemented using
    the technique of recursion, not that it is computable. Since we're
    throwing around Wikipedia links, see the definition in the first
    sentence at:

    http://en.wikipedia.org/wiki/Recursion_%28computer_science%29

    In fact, the mathematical definition would not be useful for
    programming since to us a function is an implementation of an
    algorithm (I expect Lispers may quibble over this, but it is true even
    there). Thus, in programming, all functions are computable.
    Of course I grant that the adjective 'recursive' is used differently
    in computability and in programming but the roots are not all that
    different.
    Not just the adjective 'recursive', but also the noun 'function'. I'm
    not sure of the exact etymology of 'recursive', although I would bet
    that the mathematical usage came first and the programming usage is a
    derivative of it.
  • Rusi at May 18, 2011 at 3:15 pm

    On May 18, 7:32?pm, Ian Kelly wrote:
    On Wed, May 18, 2011 at 1:10 AM, rusi wrote:
    Um, it is. ?Consider the simple function (lambda x, y: x + y).
    Mathematically, this function is recursive. ?Algorithmically, it is
    not. ?Do you disagree?
    See the definition of primitive recursion eg.
    http://en.wikipedia.org/wiki/Primitive_recursive_function#Definition
    (2 of the second set of "more complex" definitions) from where the
    name 'primitive recursion' is presumably derived)
    And for the more general (wider) class of 'recursive' functions (in
    the math sense aka computable functions) see a little below:
    http://en.wikipedia.org/wiki/Primitive_recursive_function#Relationshi...
    I know what primitive recursive and computable functions are, thanks.
    Myself, my memory of things studied badly decades ago may be
    fuzzy :D )

    Anyhow taking those links to be authoritative, what I am saying is:
    Coming from the computability side, there are 3 related but distinct
    definitions of recursive:

    1. Anything computable is recursive -- general recursive or partial
    recursive
    (evidently there is some dispute re these definitions
    http://mathworld.wolfram.com/RecursiveFunction.html
    2. Primitive recursive -- ie any function that is defined using
    - constant
    - successor
    - projection
    - composition
    - primitive recursion
    [This definition is recursive in a bad sense but let that be... The
    first use of the term is for the set of functions such that...
    The second is for a specific operation. Comes to the third use:

    3. The *operation* of primitive recursion is exactly what programmers
    call recursion.

    In other words one specific and characteristic operation is used to
    give the name to the set being defined.
    What you're failing to explain is why you would consider that function
    to be recursive from a programming standpoint. ?
    As for putting + under the format of primitive recursion, it would go
    something like this (I guess)

    Matching up that definition
    Put
    h is what is being defined ie + (or plus)
    k = 1
    f = id
    g(y, ic, x) = S(ic) #ignore y and x, ic is internal (recursive) call

    Gives

    plus(0, x) = x
    plus((S y), x) = S(plus(y, x))
  • Ian Kelly at May 18, 2011 at 3:43 pm

    On Wed, May 18, 2011 at 9:15 AM, rusi wrote:
    What you're failing to explain is why you would consider that function
    to be recursive from a programming standpoint.
    As for putting + under the format of primitive recursion, it would go
    something like this (I guess)

    Matching up that definition
    Put
    h is what is being defined ie + (or plus)
    k = 1
    f = id
    g(y, ic, x) = S(ic) #ignore y and x, ic is internal (recursive) call

    Gives

    plus(0, x) = x
    plus((S y), x) = S(plus(y, x))
    You're still arguing mathematics. I am not disputing that the
    addition function is primitive recursive (in fact, I asserted that in
    my original reply). What I am saying is that this *implementation* of
    the addition function:

    def add(x, y):
    return y if x == 0 else add(x-1, y) + 1

    is recursive in the programming sense (i.e. it uses the programming
    technique of recursion), while this implementation is not:

    def add(x, y):
    return x + y
  • Hans Georg Schaathun at May 18, 2011 at 8:12 am

    On Tue, 17 May 2011 15:26:42 -0700 (PDT), Xah Lee wrote:
    : 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

Related Discussions

People

Translate

site design / logo © 2022 Grokbase