V
Victor Eijkhout
Harrison Hill said:
If you tell a joke, you have to tell it right.
Recursion: (N). See recursion. See also tail recursion.
Victor.
If you tell a joke, you have to tell it right.
Recursion: (N). See recursion. See also tail recursion.
Victor.
H
Hans Georg Schaathun
["Followup-To:" header set to comp.lang.python.]
On 18 May 2011 09:16:26 -0700, Thomas A. Russ
: 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.
On 18 May 2011 09:16:26 -0700, Thomas A. Russ
: 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.
C
Chris Angelico
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
R
Raymond Wiker
Hans Georg Schaathun said:
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.
Except that the chain of parent pointers *would* constitue a
stack.
H
Hans Georg Schaathun
["Followup-To:" header set to comp.lang.python.]
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.
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.
C
Chris Angelico
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
P
Pascal J. Bourguignon
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.
R
Raymond Wiker
Hans Georg Schaathun said:
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.
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.
For this particular operation, possibly. For other tree
operations, a single parent pointer may not be sufficient.
X
Xah Lee
Xah wrote:
〈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 **** 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 mightdelete 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
〈English Idiom in Unix: Directory Recursively〉
http://xahlee.org/comp/idiom_directory_recursively.html
Mike Barnes said:
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 **** 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 mightdelete 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
H
Hans Georg Schaathun
["Followup-To:" header set to comp.lang.python.]
> 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.
> 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.
J
John Nagle
The proper terminology is "subtree", "subfolder", or "subdirectory".
John Nagle
H
Hans Georg Schaathun
["Followup-To:" header set to comp.lang.python.]
> 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 **** 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.
> 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 **** 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.
L
Lanarcam
Hans Georg Schaathun écrivit:
Traversing recursively a directory is more readily understandable when
there are sub-directories, the operation involves going down those
sub-directories and applying the same function ad infinitum.
Excuse my Latin.
Traversing recursively a directory is more readily understandable when
there are sub-directories, the operation involves going down those
sub-directories and applying the same function ad infinitum.
Excuse my Latin.
R
Raymond Wiker
Hans Georg Schaathun said:
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.
M
Mike Barnes
Xah Lee said:
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.
M
Martin P. Hellwig
I concur, although my dictionary defines the base of the word:
"to happen many times or to happen again"
http://dictionary.cambridge.org/dictionary/british/recur#recur__3
Perhaps the gp of the post might profit from a more holistic approach
when adopting an opinion or at least consult a dictionary before going
into a rant.
H
Hans Georg Schaathun
["Followup-To:" header set to comp.lang.python.]
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.
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.
R
Rikishi42
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.
T
Thomas A. Russ
Ignored, since I don't follow that group.Hans Georg Schaathun said:
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.
T
Thomas A. Russ
Pascal J. Bourguignon said:
Um, this is a recursive function. Inside PARENT, there is another call
to PARENT.