English Idiom in Unix: Directory Recursively

[Xah Lee]

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

 

[Ian Kelly]

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]

     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]

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]

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 )

 

[rusi]

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

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

 

[Thomas A. Russ]

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

 

[Harrison Hill]

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

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.

 

[Ian Kelly]

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]

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

 

[rusi]

Rusi wrote

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

 

[Hans Georg Schaathun]

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.

 

[Espen Vestre]

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.

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)

 

[Hans Georg Schaathun]

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

 

[Mike Barnes]

For example, when you want to delete the whole dir in emacs, it
prompts this message: “Recursive delete of xx? (y or n) â€.

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.

 

[rusi]

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

 

[Ian Kelly]

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

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]

I know what primitive recursive and computable functions are, thanks.

Myself, my memory of things studied badly decades ago may be
fuzzy )

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]

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

 

[Thomas A. Russ]

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

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.