We’ll start with pig Latin. To translate a word to pig Latin, you move its initial consonants to the end of the word, so that it starts with a vowel, and then append “ay”. So, “snap” in pig Latin is “apsnay”.
(This is a simplified version of the translation algorithm you learned as a kid. For one thing, sometimes you have to consider Y to be a vowel, because otherwise a word such as “sky” doesn’t have any vowels. But we’ll ignore that to keep the program simple.)
You don’t have any problem with one function calling another function, such as PIG LATIN calling VOWEL?, right? The first function waits while the second function does its work, and then the first function carries on, using the value returned by the second one. You can imagine that inside the computer there are lots of little people, each of whom specializes in carrying out one procedure, so there’s a little person named Peter who knows how to do PIG LATIN, and one named Violet who knows how to do VOWEL?. Peter asks Violet whether the first letter of the word is a vowel, Violet answers True or False, and then Peter can give that answer to Isobel, who knows how to do IF.
Well, recursion is exactly the same idea, but one little person asks another little person who specializes in the same procedure to solve a subproblem.
So, to write PIG LATIN you have to realize that the translation of “snap” into pig Latin is the same as the translation of “naps” – the word with just the first letter moved to the end of the word. And then, the translation of “naps” is the same as the translation of “apsn”. But “apsn” starts with a vowel, so we can just append “ay” to get “apsnay”.
So, you ask Peter for the pig Latin for “snap”. Peter asks Pamela for the pig Latin for “naps”. Pamela asks Pavel for the pig Latin for “apsn”. And Pavel takes the first branch of the IF, because “apsn” starts with a vowel.
What gives people trouble about recursion is that they try to understand the recursive call as meaning “go back to the top of the procedure,” like this:
This iterative version works, too, but only because PIG LATIN uses a particularly simple version of recursion, called “tail recursion,” in which the recursive call is the very last thing the procedure has to do. When students have trouble understanding recursion, it’s almost always because they are mentally translating the recursive version into the iterative version, and that stops working when you encounter non-tail recursion. Instead you have to think about little people, and understand the recursive call as two separate little people, Peter and Pamela (or Pamela and Pavel), independently running the same code.
Okay, on to non-tail recursion. People often find it easier to start with an imperative recursion rather than a functional one, so we’ll start by drawing a tree like this:
That’s a level-four tree, i.e., it has branches on branches on branches on the trunk of the tree. We’re going to work up to that in stages, so first we draw a level-one tree, which is just the trunk. But (planning ahead) we want to leave the turtle in the same place it started:
Okay, on to a level-two tree. We could write it this way:
Note in passing that it’s now clear why we have to move back after moving forward: After drawing the left branch, we need the turtle to be in the correct position to draw the right branch.
But for levels higher than two, coding each branch with MOVE blocks would be too horrible to contemplate. So, notice that in the level-three tree, the left branch is a level-two tree:
So we can code the level-three tree in a way that takes advantage of that understanding:
(I’m going to stop showing the toplevel script; you get the idea of those. Also, a pedagogic side note: Arguably the TREE procedures belong more in the Motion category than in the Pen category, but putting them in Pen makes what will become the recursive calls stand out visually in the script.)
Note that when we hire Trevor to draw a TREE3 of size 100, he hires Tabatha and Tom to draw TREE2s of size 75. Each little person has his or her own idea of what SIZE is. Saying that another way, each little person has his or her own local variables. We can imagine that each TREE3 and TREE2 little person has a pocket labelled SIZE that has some number in it.
From here, we can straightforwardly code higher-level trees:
These procedures aren’t recursive; each one calls a lower-level helper procedure. So you should have no trouble convincing yourself that they all work. There’s a lot of procedure calling going on, though; if you draw a TREE5, you need 16 little people who know how to draw a TREE1.
Which reminds me: I’m going to rewrite TREE2 so that it looks like the others:
So, in principle, we can make arbitrarily complicated trees by making blocks TREE6, TREE7, and so on. But it’d be too horrible to contemplate if we wanted to make a level-100 tree that way!
Instead, we notice that all these procedures look almost the same; it’s just the two calls (left and right branches) to the next-lower-level TREE procedures that differ. So the big insight is that by adding another input we can capture that difference and collapse them all into one block:
Unfortunately, this procedure doesn’t work. It keeps trying to draw smaller and smaller left branches, so the turtle ends up spinning around at the top:
This is a typical student bug in using recursion. The problem is that it isn’t quite true that all the numbered TREE procedures are the same. The first one is different from the others:
TREE1 does its work all by itself, without calling a (nonexistent) TREE0 procedure. A level-one tree doesn’t have left and right branches; all it has is a trunk. This illustrates a general rule of recursion: there has to be a base case that the procedure knows how to handle without calling itself recursively. So the correct TREE procedure looks like this:
Every recursive procedure needs a base case. In PIG LATIN, the base case is that the word starts with a vowel.
Don’t forget that even though they’re all running the same code, each TREE person has his or her own SIZE pocket. So when we hire Tammy to draw a TREE8 of size 100, she hires Terry to draw a TREE7 of size 75, but Tammy’s SIZE pocket still has 100 in it. It doesn’t change to 75! This is why you can’t mentally translate the recursion into a loop like
the way you could in the case of PIG LATIN. This is a general rule: Any time you find yourself thinking the words “go back” in computer programming, you’re in trouble. You have to think little people instead.
Almost done. Recursive reporters (functions) are just like recursive commands, except that the recursive call(s) are embedded in a larger expression. So, here’s a procedure to list the moves to solve the Towers of Hanoi problem:
(Again, I’ve chosen to put the block in an unnatural category so that the recursive calls stand out.) The base case is a one-disk tower; you just move the one disk where you want it. With more than one disk, you first move the top n-1 disks out of the way, then you can move disk n, and then you move the other n-1 disks on top of it.
If you want all this spelled out more slowly, you can read my Logo books:
or my Scheme book:
(In both cases, the link points to the first of several consecutive chapters about recursion.)
