On May 18, 7:06 am, rusi <rustompm...@gmail.com> wrote:
> 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...
No need - I have the Dictionary definition of recursion here:
Recursion: (N). See recursion.
--
http://mail.python.org/mailman/listinfo/python-list
