Re-teaching Recursion

This post is intended for software developers. There's a software developers' joke that says "to understand recursion, you must first understand recursion".  That joke is mildly amusing if you understand recursion, but incomprehensible if you don't know it.  Good teachers obsess a little bit about the best way to teach the concept of recursion. As someone who teaches software developers, I'm always looking for images and jokes that help software developers understand the topics I teach.

What recursion is

Recursion is not particularly hard; it is simply unfamiliar because it is a math/software approach not used much in other parts of real life.  Recursion just means "some function that invokes (calls) itself". Few things in the real world work like that.  The first step in "build a house" is not and cannot be "build a house".  So how does recursion work for software? 

The key is that a recursive function first does a little bit of work to reduce or simplify the problem, before calling itself to handle what is left. A recursive approach starts with a big problem; it reduces the big problem slightly, and then calls itself to handle the now smaller problem. The first step in building a house might be "excavate foundations" followed by "build rest of house". You would pass an argument to the next call, giving the current state of the house. The function "build rest of house" will look at what still needs to be done, and cycle through those steps using further calls to itself. That is a recursive algorithm. 

The graphic at the top of this page doesn't adequately capture that the recursive call creates a smaller problem to solve, and that the smaller problem is further reduced in scope in each successive recursive call.  Here's an image I saw recently, that does (sort of) suggest the problem is reduced in size at each step.

An old lady is operating a puppet of herself, to feed a squirrel.  Now imagine she wanted to feed an ant. She could make a second, much smaller puppet, controlled by the first puppet, to feed the ant.  If she wanted to feed an amoeba, she could create a third, even smaller puppet, that is controlled by the second puppet. And that captures the essence of recursion, although not the practical application.  This was the picture I stumbled across while thinking about recursion.  If I showed it to my class, maybe it would help students "get" recursion in a visual way.

I was quite pleased with this idea, and posted about it on Google+.  One of my friends quickly added a comment that he recommended people follow a link he posted, to learn more.  His link pointed to the same post readers were already on ... [His link was a more subtle version of the one liner joke at the start of this post].

The picture below represents recursion with a real world problem.  If you need to find out how many people are in some organization, you might go to the office chief and ask them to ask all their direct reports this question, "please tell me how many direct reports you have, and please ask each of your direct reports to ask the same question of their subordinates (how many direct reports they have) and so on down the management chain". The question should percolate through all layers of management until it reaches groups that don't contain any more managers, and the answers start coming back. All you need do is add all the numbers to get the final headcount. Voilà, recursion.

You never have to use recursion. Every software problem that can be solved with recursion, can also be solved with iteration (i.e. a loop with a counter). But sometimes recursion exactly matches a data structure (like lists, trees, or queues), or simplifies the expression of a problem.  That's when to use it!

Factorials are frequently used as the model example of recursion. The factorial of the number five (written with an exclamation mark, like 5!) means 5 multiplied by all the integers below it, down to 1. So

5! = 5 * 4 * 3 * 2 * 1.   

The value of N! is clearly N * (N-1)!  E.g. 5! is equal to 5 * 4!.  You can create a factorial calculator by writing an expression that multiplies N by the result of a recursive call with N-1 as the argument. The pseudo code will look like this:

       function calc_factorial( integer N ) {

if N equals 1 then return 1  /* base case to end recursion */

result = N * calc_factorial(N - 1)  /* recursive call on reduced arg "N - 1" */

           return result

       }

(You can actually return a value when you count down to 2, because multiplying any number by 1 doesn't change it).  

Every recursive routine has:

1. a "reduce" part that makes the problem smaller or simpler.
2. a "recursive call" to itself, with the smaller, simpler argument. It may call itself directly, or indirectly through another function.
3. a "base case" (exit criteria) to end the recursion and return the calculated result so far.

If if get enough interest, I'll write another recursion post, with some code examples. So feel free to post comments below.

Chestnut

Although it is an old chestnut among programmers that "to understand recursion, you must first understand recursion", it is still a much loved gem.  Even Google couldn't resist the temptation. Try googling the word "recursion" to see what I mean.  You'll get a result like the screenshot below. It's a regular laugh riot with the chuckle-meisters down at the Google mill.

I write plenty of technical content for software-knowledgable audiences. Need help with a developer blog, white paper or other technical content? Send me an email through linkedin.

Peter