[Solved]: Teaching Recursion

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 Out1. Mathematically sophisticated readers might recognize the Recursion Fairy by its more formal name, the Induction Hypothesis. 1: 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.