Up: Recursion. Prev: About the Towers puzzle. Next: A solution program.

What is recursion?

Recursion is the concept of well-defined self-reference. We use recursion frequently; consider, for example, the following hypothetical definition of a Jew. (This definition isn't official - it's just something I heard at a party once.)

Somebody is a Jew if she is Abraham's wife Sarah, or if his or her mother is a Jew.
So if I want to know if I am a Jew, I look at this definition. I'm not Sarah, so I need to know whether my mother is a Jew. How do I know about my mother? We look at the definition again. She isn't Sarah either, so we ask about her mother. We keep going back through the generations - recursively.

Self-referential definitions can be dangerous if we're not careful to avoid circularity. The definition ``A rose is a rose'' just doesn't cut it. This is why our earlier definition of recursion includes the word well-defined.

We can write pseudocode to determine whether somebody is a Jew:

FUNCTION isAJew(person):
IF person is Abraham's wife Sarah, THEN:
    return true
ELSE:
    return isAJew(person's mother)
END IF
This is a recursive function, since it uses itself to compute its own value.

Eventually we will write a recursive function for Towers of Hanoi, but let's look at our isAJew function a bit closer for the moment.

Notice that there's a case (namely, when person is Sarah) when the function does not call itself recursively. This is called a base case. Every function must have a base case; otherwise, the function will keep calling itself and will never get around to returning a value. The program will either crash or it will continue until an external effect stops it; it will certainly not find the right value.

You may have noticed that our isAJew function itself has this problem. What if I am not a Jew? Then we'll ask about my mother, then her mother, then her mother, and so on. We'll never reach Sarah, and the list of mothers will go much further back. We'll never stop. (In this case, we'll crash at some point (maybe when we try to find Eve's mother).) The problem here is that we're missing a base case.

To repair this, we add a new base case.

FUNCTION isAJew(person):
IF person is Abraham's wife Sarah, THEN:
    return true
ELSE IF person was born before Sarah was born, THEN:
    return false
ELSE:
    return isAJew(person's mother)
END IF
As this example demonstrates, recursion can involve subtle problems, but it's often useful or even essential.

Why discuss recursion at all in the context of Towers of Hanoi? Because recursion is the essential technique that is by far the easiest way to explain how to solve the puzzle. Before going on and spoiling the fun, try yourself to think of a way to define the pattern you use to solve the Towers of Hanoi puzzle.

Next: A solution program.