Teaching Recursion

Question

I'm a teacher assistant in my university and my next topic is recursion. what way is the best to teach recursion so that the student can grasp the concept easily and can think recursively?
I was thinking about explaining the stack structure to teach recursion but I'm worried that they get stuck in tracing the process. any hint?

Answer 1

My favorite way to teach recursion is by reference to the Recursion Fairy.

I'm sure we're all familiar with the idea that stories can be a very effective way to teach ideas; people seem built to hear and remember stories. The Recursion Fairy is an explanation suggested by Jeff Erickson, which lends well to this approach.

As Jeff E. writes:

Recursion is a a particularly powerful kind of reduction, which can be described loosely as follows:

• If the given instance of the problem is small or simple enough, just solve it.
• Otherwise, reduce the problem to one or more simpler instances of the same problem.

If the self-reference is confusing, it’s helpful to imagine that someone else is going to solve the simpler problems, just as you would assume for other types of reductions. I like to call that someone else the Recursion Fairy. Your only task is to simplify the original problem, or to solve it directly when simplification is either unnecessary or impossible; the Recursion Fairy will magically take care of all the simpler subproblems for you, using Methods That Are None Of Your Business So Butt Out¹. Mathematically sophisticated readers might recognize the Recursion Fairy by its more formal name, the Induction Hypothesis.

¹: When I was a student, I used to attribute recursion to “elves” instead of the Recursion Fairy, referring to the Brothers Grimm story about an old shoemaker who leaves his work unfinished when he goes to bed, only to discover upon waking that elves (“Wichtelmänner”) have finished everything overnight. Someone more entheogenically experienced than I might recognize them as Terence McKenna’s “self-transforming machine elves”.

I recommend reading his entire lecture notes on recursion. They are a thing of beauty and will give you many excellent ideas for how to teach recursion.

For instance, check out his explanation of the Towers of Hanoi, where he shows how to solve the problem by recursion. My favorite part:

The trick to solving this puzzle is to think recursively. Instead of trying to solve the entire puzzle all at once, let's concentrate on moving just the largest disk. [...] And then after we move the $n$th disk, we have to move those $n-1$ disks back on top of it. So now all we have to figure out is how to...

STOP!! That's it! We're done! We've successfully reduced the $n$-disk Tower of Hanoi problem to two instances of the ($n-1$)-disk Tower of Hanoi problem, which we can gleefully hand off to the Recursion Fairy (or, to carry the original story further, to the junior monks at the temple).

---

References to the Recursion Fairy: A Youtube video ("Recursion is when you need to solve something, you call on yourself instead of others!" "So when I have a problem, I ask myself to solve it?" "In order to understand recursion, one must understand recursion"). Divide-and-conquer is an Army of Recursion Fairies.

Answer 2

I find that the best way to explain non trivial recursion is to start with mathematical functions, which are more "comfortable" for some of the students. For example, Fibonacci numbers are an excellent example, since they use two recursive calls.

Another example (which can be given as a simple exercise) is to compute $n!$.

Then, some more "algorithmic" examples are in order, on more involved data structures. The most natural examples here are tree traversals (pre-order, in-order, post-order). I think that after these examples, the students get the hang of it. From there on, it's mainly practice.

I would save the stack structure for later, as it is more relevant to the way recursion is actually implemented in computers, which has less to do with the actual concept of recursion.

Answer 3

Shaull's suggestions are good. It's important to keep in mind, and continually remind the students that the underlying idea is:

To solve a problem: (1) deal with the base case(s), where recursion doesn't apply, and (2) solve everything else by solving smaller problem(s) and suitably combining the smaller solutions into your solution for the original problem.

This works well for numeric problems, like computing $n!$ (where the smaller problem involves computing $(n-1)!$) or computing $x^n$ using repeated squaring (where the smaller problem is, basically, computing $x^{n/2}$).

Recursion and induction go hand in hand, especially when proving correctness of a recursive algorithm or when getting timing estimates for one.

Recursion is a natural technique for trees, of course, but don't forget about lists, as well, doing things like recursively summing a list of numbers or reversing a list. Of course mergesort is a natural candidate here and it's worth the effort to do it all recursively, including a recursive implementation of splitting a list into two nearly-equal parts and implementing the merge portion recursively.

I like to point out that besides being a powerful design tool, recursion is worth study since there are problems where the non-recursive solution can be exceedingly hard to come up with. A good example of this is the Towers of Hanoi: the recursive solution is simple and more or less transparent, while a non-recursive solution is really difficult to explain and, probably, even harder to invent in the first place.

Answer 4

When teaching recursion, you may want to start with functions or with data-structures.

As I recall from my teaching days, I used to start with a cooking structure: the onion. So I explained that a onion is either a lonely peal (or a kernel), or an oinion with a peal around it. Then I switched to other structures such as strings or trees.

Then I had to write programs for these structures. And they naturally called themselves recursively, following the definition of the structure. The base case concept also appears more natural, and the approach avoid having the concept of simpler instances of the problem, at least at first.

Applying it to other data such as numeric data is then more natural.