[net.lang] Difficulty of recursion

dfz (03/22/83)

Your "cheese stands alone" argument is amusing but misleading.  What you
have demonstrated is the difficulty of understanding explicit use of a
stack.  While it is true that recursion is often implemented using stacks,
it is not necessary for the user of recursion to have any knowledge of
such implementation.

I believe you will find that the languages of the future will rely heavily
on recursion rather than iterive constructs, for several reasons:

	1. recursion is more concise

	2. recursive algorithms tend to make the structure of
	   the problem obvious; iterative algorithms tend to hide it

	3. recursion automatically breaks up a problem into a hierarchy
	   of independently executable modules;  such modules can
	   therefore be executed in parrallel on a machine of suitable
	   architecture (none exists yet); iterative techniques offer
	   little hope for parallelism; parallelism will open for us
	   a new dimension of performance

				Dave Ziffer
				..!decvax!ihnss!iwlc7!dfz

mat (03/22/83)

There have been arguments posted to the effect that recursion is/is not
a natural way to program, and an easy way to learn to program.

Here is the revalation:

	Recursion is a natural way to program solutions to problems
	whose structures are easily defined recursively.

	Problems which are more naturally iterative (single lists
	rather than trees) are probably more easily handled by iteration.

	Recursion CAN simplify problems; it can also confuse them.
	Handling the inductive aspect of recursion may be easy ONCE
	the principles are grasped.  To teach these principles to
	new programmers with a limited background in finite math, etc,
	AS AN INTRINSIC part of programming will very likely distract
	from many of the real difficulties involved.

	In short, if you are teaching a math major how to program,
	recursion will probably come easily.  If you are teaching it
	to a four--year--old, then if his programming skills are
	limited to moving turtles in interesting patterns, it doesn't
	matter too much, he will have plenty of time to learn the
	other parts of the art of programming.  If, however, you wish
	to teach someone how to program productively for a wide
	variety of problems, and that person does not already have
	a couple of potloads of problem solving skills at his disposal,
	you are going to have to start by working from things that
	HE (/SHE/IT) understands.
						Mark Terribile
						Duke of DeNet
						...!hou5e!mat

ajh (03/23/83)

Is recursion all that difficult?  I don't think so.  When
I was 12, I took an assembly language class with almost no
prior computer experience.  One assignment was to calculate
fibonacci (sp?) numbers using recursion.  I spent about three
days hacking at it to no avail, so I asked the professor.  In
about five minutes, everything boiled together and it all made
sense.  Since then, I've seen recursion explained many ways.
Those who explain it simply seem to be able to teach it to others
easily.  Those who call it a "funny" way to write code never seem
to be able to teach it to anyone else.  (Incidently, I sat in on
a Pascal class where the professor taught recursion during the
first session.  Later, when he introduced iteration, all the students
asked,"Why not use recursion?  This is really bizarre.")  The
moral is that recursion isn't hard, it just has to be explained well.

Will compilers stop kids from learning about computers?  Again,
I don't think so.  When I was in seventh grade, I learned Pascal.
Although I didn't like waiting for the compiler, I didn't become
a lawyer, either.  Now, I can't speak for all kids, but for me,
compiling was no big deal.  Kids will want to learn no matter how
hard you try to stop them.

Do interpreters teach bad habits?  I don't think its the interpreter
as much as the language.  BASIC, for example, tends to discourage
commenting.  A well commented program will take several times the
execution time.  Furthermore, it makes writing modular code difficult.
The gosub-return sequence provides for no parameters or local variables.
My friends who were weaned on BASIC tend to produce sloppier code than
those who were weaned on a structured language.  That may just be their
own fault, but I think the language has something to do with it.

Oh well, enough rambling.  That's my $0.01x10^-23 worth.

				Alan J. Hu
				ucbvax!sdcsvax!ajh (or something like that.)