Xref: utzoo comp.edu:3712 uw.general:1958
Path: utzoo!attcan!lsuc!watmath!att!att!pacbell.com!ucsd!usc!samsung!dali.cs.montana.edu!milton!Tomobiki-Cho!mrc
From: mrc@Tomobiki-Cho.CAC.Washington.EDU (Mark Crispin)
Newsgroups: comp.edu,uw.general
Subject: Re: Recursion Summary
Message-ID: <9948@milton.u.washington.edu>
Date: 26 Oct 90 00:14:02 GMT
References: <1990Oct23.211651.10227@contact.uucp> <9868@milton.u.washington.edu> <9882@milton.u.washington.edu> <9893@milton.u.washington.edu> <9898@milton.u.washington.edu> <13510@june.cs.washington.edu>
Sender: news@milton.u.washington.edu
Distribution: na
Organization: Mendou Zaibatsu, Tomobiki-Cho, Butsumetsu-Shi
Lines: 62


The problem is that there are two definitions of "recursion".

Let's leave the real of mathematical formalism and talk about the real
world.  This may be difficult for some CS students, judging from the
results of a typical systems qual.  [I can't believe so many CS
students fail systems quals -- the ones I've seen have been *trivial*
modulo the obligatory
	Define: A is `strongly hyperhyperimmune' if A is infinite and there is
	no recursive f such that (u)[W(f(u))  A  empty] & (u)(v)
	u  v => W(f(u))  W(f(v)) = empty].
	A. show that if A is strongly hyperhyperimmune then A has no
	   infinite retraceable subset.
	B. show that if A is strongly cohesive then A is strongly 
	   hyperhyperimmune.
type of problem.]

In the pure mathematical definition of "recursion", then nothing on
today's typical stored-program digital computers is recursive.  This
*includes* the C and Lisp programming languages.  Yet both C and Lisp
are known for their "recursive" properties.

It is meaningless to talk about the pure mathematical definition of
recursion in the same breath with C or Lisp algorithms or the
recursive programming facilities of those languages.  Remember, the
original question was something like "why do I need to use recursion
when programming?"

So, what other definition of "recursion" is there?  The definition
used in C and Lisp.  The one that programmers actually use.  The one
that's served me well in 17 years of operating system/multi-tasking
applications programming.  It looks to the programmer a lot like
mathematical recursion, but in fact (as has been pointed out) it is in
fact iterative.

In a multi-tasking application -- an operating system, or one which
uses daemons (common in object-oriented languages such as Lisp or the
various object-oriented extensions to C) -- a recursive algorithm is
often the only algorithm which can be practically implemented.  Not
because an iterative algorithm is impossible, but because it is too
complex.  It gets worse when the algorithm must interact with other
algorithms and co-routining enters the picture.

In fact, I'll go further, and say that iteration is nothing more than
an optimized form of tail recursion.  Recursion in the programming
sense, not the mathematical sense.

Yes, for simple algorithms, recursion is a handy shorthand and you can
use iteration.  But I could give you some recursive algorithms that I
doubt you'll be able to write a working iterative version (much less
one that can be readily modified).  So what if the computer executes
the instructions serially?  Some machine in the future may not.  For
the most part, the details are hidden from the programmer as it should
be.  Computers are to make the job easier, not more complicated.

 _____   | ____ ___|___   /__ Mark ("Gaijin") Crispin  "Gaijin! Gaijin!"
 _|_|_  -|- ||   __|__   /  / R90/6 pilot, DoD #0105   "Gaijin ha doko?"
|_|_|_|  |\-++-  |===|  /  /  Atheist & Proud          "Niichan ha gaijin."
 --|--  /| ||||  |___|    /\  (206) 842-2385/543-5762  "Chigau.  Gaijin ja nai.
  /|\    | |/\| _______  /  \ MRC@CAC.Washington.EDU    Omae ha gaijin darou"
 / | \   | |__|  /   \  /    \"Iie, boku ha nihonjin." "Souka. Yappari gaijin!"
Hee, dakedo UNIX nanka wo tsukatte, umaku ikanaku temo shiranai yo.