On May 18, 9:51 am, Roland Hutchinson <my.spamt...@verizon.net> 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...
--
http://mail.python.org/mailman/listinfo/python-list
