Is induction or recursion easier to understand?

Question

This is not really a new question, more a revisiting of @vonbrand's "Any suggestions on how to approach recursion and induction?" In an introductory programming class this past year, I asked the students to create a Mondrian-like image via recursion. Here is a typical submission:

---

       

---

These 1st-yr college students had little difficulty understanding the recursion necessary to produce such images. Most of them had little beyond US high-school mathematics—maybe calculus, no discrete math, no proofs. And yet at the same time I taught more advanced students induction in the theory of computation, and it was a mental hurdle for most of them.

Despite the informative answers to "Why are induction proofs so challenging for students?," I am still uncertain. The Mondrian experience has made me wonder if it might not be better pedagogically to introduce recursion first, nail that down thoroughly, and then teach induction—the apparently more difficult concept—by connecting to and building upon their understanding of recursion. This may work even for students who have no programming experience, and are taught recursion "theoretically."

Answer 1

One thing that you have to keep in mind here, is that you don't need to understand recursion to implement it. There is a big difference between "we were taught to do it like that, I implement it and it works" and really understanding the concepts and why it works as it does. With induction, on the other hand, you are supposed to write down a complete, formal proof, so you need at least better understanding of the concepts, if possible you should understand completely why it works.

Regarding your question if you should teach recursion or induction first, I would suggest this order:

1. Teach recursion and let the students program recursive functions.
2. After the students saw that it worked, focus on the theoretical concepts. For example give them a short recursive program and ask them to prove what it computes on a given input. Or go back to the problems programmed before and ask the students to prove that they really do what they are supposed to.
3. Show the students that for such proofs, it is easier to build them up from the bottom, i.e. not showing "on input $n$, we do this and that and use the function on $n-1$. Here, on input $n-1$, we do..." but rather starting with $n=1$.
4. Let them train induction and recursion parallel. For example assume that the students should show $$\sum_{i=1}^n i = \frac{n(n+1)}{2}.$$ Let them write a recursive program, computing the left hand side (that should be a rather easy program...), then apply the methods learned above to show that this program actually computes the right hand side.
5. Gradually drop the programing tasks and focus more on the proofs.

In this way, the students don't just get induction as a strange, abstract concept, they have a practical component in learning it. They can learn that a proof is not something strange, it's just a formalized way to show something (in this case: "my program does what I claim it does"), show them that this formalism is not something to fear but is rather making it easier to show the correctness of their recursive programs and statements. In this way, you might actually be able to get them to understand that a formal proof is something good; this knowledge will be useful far beyond your course on induction.

Disclaimer: I am assuming an optimal class. In practice, some of these things might not work so well due to time limits or unmotivated students.

Answer 2

As a disclaimer, I am a CS teacher, so I teach both concepts within that context. However, there is no doubt in my mind that induction is far harder for students to grasp. I have not been able to figure out why.

Part of the problem with induction is that there are simply so many moving parts. The inductive step can be quite complex (particularly in my field, where we also need to teach about loop invariants), and at the start, it always seems to me that the student think that we are somehow trying to prove that $n = n+1$. It takes a long time for that particular fog to lift. And, most importantly, none of it makes sense until the entire thing gels, so partial understandings don't lead to any real understanding.

By contrast, I can often get my kids to develop recursion on their own by asking them how they would figure out the size of a directory.

Answer 3

In the context of programming, it seems more natural to distinguish recursion from iteration than from induction, as iteration is the algorithmic realization of iteration.

In the context of mathematical proof, recursion becomes something like the method of infinite descent (e.g. the classic proof of the irrationality of $\sqrt{2}$), and is quite natural for proving something like the Euclidean algorithm for the greatest common divisor.

In either context, students struggle with the notion that requires consideration of a potentially infinite process. The principle of induction asserts something psychologically difficult, that showing that case $i$ implies case $i+1$ shows something for all $n$, no matter how big. The basis of recursion is that some sort of backwards iteration cannot continue infinitely downwards. Students are accustomed to considering a single step, and nothing more.

Whether it makes more sense to emphasize descent/recursion or induction/iteration surely depends on the educational context and goals.

The recursive approach to understanding Euler's method may be important conceptually for understanding the mathematics of unique factorization in a principal ideal domain. My experience in basic programming classes is that students initially have a lot of difficulty programming it recursively. Their naive approach is the brute force iterative check (to find the gcd of $a < b$, start dividing both by $a$, then $a-1$, etc.). The iterative approach is more accessible, and for many students it probably needs to be tried first, before the recursive approach can be understood. It's important for students to digest that such apparently different approaches resolve the same problem.

In a programming context, recursion requires understanding that a function (or some similar construct) can call itself and this is difficult for many students who have never (well) understood the idea of functions in any context. An iterative procedure is by its nature step-by-step, and this is how most students have been taught. More fundamentally, it requires (in practice) no operational functional concept, just repetition of a set of instructions with a change of a parameter. Also, in practice recursion can involve dealing with issues of memory use (the stack) that require more sophistication (from a programming point of view).

Finally, I wonder if in mathematically oriented programming contexts recursion is sometimes over emphasized (probably because of its aesthetic appeal). From a mathematical point of view the issues of computational efficiency and complexity are important, both pedagogically and practically, and often (always?) iterative implementations can both be made faster in execution and more parsimonious with memory than recursive implementations.