pavel (03/19/83)
Mark Horton's claim (now stated at least twice in this discussion) is that recursion is "VERY hard" for beginners to learn. I must take exception. Many of you will, I'm sure, agree with Mark; you've never known anyone to pick up recursion very quickly and every time you tried to teach it to any- one, they found it very strange and foreign. I believe I can give both a partial explanation for this behaviour and also some personal experience which contradicts this pattern. (Before I begin, let me point out that I'm not a LISP hacker; I have written exactly one complete program in LISP, for a class, which was under 2 pages long.) Remember back, if you will, to your own first experience with recursion (or proof-by-induction; they're entirely equivalent concepts). If your experience was like most, you had already been taught the rest of some appropriate language, like PASCAL, including all of the iterative constructs. Your instructor then proceeded to explain to you this "strange" way of writing programs. They told you it would be hard (but stick with it) and they seemed at times to not really have a firm grasp on it themselves. The first example of such programs was one of the following: 1) The factorial function That's right, they almost certainly gave you factorials as your first example. Here was a function that you'd probably already coded up iteratively, that you understood perfectly well iteratively, and now they're trying to make you do it in this funny way. Why not use the "normal" kind of program, you asked yourself. Already, recursion gets associated with doing things in a "funny" way. Is it surprising that you didn't like it and never really understood it? Now consider that your instructor was probably also taught it in this way, doesn't like/understand it, and is only teaching it because they feel it's their duty. Clearly, this is the wrong way to go about it. Of course it's hard for the kids to learn it. But suppose, instead, that it's taught by someone who really understands it, appreciates its role as a program simplifier, and knows that the range of its applicability is not limited to the Towers of Hanoi and tree-walking. (Though these are programs which are much more difficult to write/read/understand using iteration than using recursion). My point here is that the perceived difficulty in learning recursion is a product of the learning "envirionment", not an intrinsic property of the concept. Evidence, you cry, evidence! Last summer, I was allowed to teach a three week course in "Computer Science" to a bunch of kids in the 12-14 year old bracket. The only requirement was that the kids learn Pascal; the rest of the course content was up to me. In three weeks, these folks went from knowing nothing about computers (most of them. Of course, some of them had PC's at home and were real BASIC jocks) to writing a recursive-descent compiler/evaluator for a simple Pascal-like language. At the usual place in the course, we took up recursion (they were going to need it in order to do the project). They were assigned the Towers of Hanoi (I'm no more original than anyone else) and were given the following rules to use in writing recursive procedures: 1) You are allowed to pretend that you have already finished writing the procedure and that it works perfectly. 2) You can therefore use the procedure to solve the problem as long as you meet these requirements: a) There must be some smallest case that you handle without using the procedure. These so-called "base cases" are almost always so simple that their solution is very obvious (e.g. what is the factorial of 1?). b) If you use the procedure, you have to give it a smaller problem than you have. After it solves the smaller problem, you can use its answer to solve the bigger one. They had already seen inductive proofs and several of the students came up to me after lecture and pointed out the similarity. This set of simple rules, which they understood (as opposed to just following them by rote), gave them all of the intuition they needed to solve the problem. We went through one example call of the factorial function using a student for each instantiation of the procedure. When they saw that the rules guaranteed that they couldn't get something for nothing, they were almost all able to go out and write the program for Towers of Hanoi. I am teaching the same course this summer. My intention is to change the format of the programming curriculum so as to teach them recursion \\before// they see any of the iteration constructs. The purpose is to get them before they've been brainwashed. I would be interested in hearing any arguments for the opposite side of this question, i.e., arguments that show that recursion has inherent difficulty. I don't believe it, but I'm always willing to listen. Pavel
mark (03/24/83)
#R:cornell:-412500:zinfandel:7000003:000:466 zinfandel!mark Mar 22 16:49:00 1983 Pavel: Please keep us posted on your experiences with teaching recursion. I learned recursion (induction) in mathematics, long before I had seen ANY programming language, in contexts where it was entirely appropriate, and far simpler then iteration (indeed, iteration often wasn't even applicable). Recursion still seems to me to be conceptually more difficult than iteration, although it's use can make a solution easier. Mark Wittenberg ...!decvax!sytek!zehntel