Computer Science Logo Style volume 1: Symbolic Computing 2/e Copyright (C) 1997 MIT

Practical Recursion: the Leap of Faith

cover photo
Brian Harvey
University of California, Berkeley

Download PDF version
Back to Table of Contents
BACK chapter thread NEXT
MIT Press web page for Computer Science Logo Style

When people first meet the idea of recursive procedures, they almost always think there is some sort of magic involved. "How can that possibly work? That procedure uses itself as a subprocedure! That's not fair." To overcome that sense of unfairness, the combining method works up to a recursive procedure by starting small, so that each step is completely working before the next step, to solve a larger problem, relies on it. There is no mystery about allowing downup5 to rely on downup4.

The trouble with the combining method is that it's too much effort to be practical. Once you believe in recursion, you don't want to have to write a special procedure for a size-one problem, then another special procedure for a size-two problem, and so on; you want to write the general recursive solution right away. I'm calling this the "leap of faith" method because you write a procedure while taking on faith that you can invoke the same procedure to handle a smaller subproblem.

Recursive Patterns

Let's look, once more, at the problem we were trying to solve when writing the downup procedure. We wanted the program to behave like this:

? downup "hello
hello
hell
hel
he
h
he
hel
hell
hello

The secret of recursive programming is the same as a secret of problem solving in general: see if you can reduce a big problem to a smaller problem. In this case we can look at the printout from downup this way:

downup hello results

What I've done here is to notice that the printout from applying downup to a five-letter word, hello, includes within itself the printout that would result from applying downup to a smaller word, hell.

This is where the leap of faith comes in. I'm going to pretend that downup already works for the case of four-letter words. We haven't begun to write the procedure yet, but never mind that. So it seems that in order to evaluate the instruction

downup "hello

we must carry out these three instructions:

print "hello
downup "hell
print "hello

(The two print instructions print the first and last lines of the desired result, the ones that aren't part of the smaller downup printout.)

To turn these instructions into a general procedure, we must use a variable in place of the specific word hello. We also have to figure out the general relationship that is exemplified by the transformation from hello into hell. This relationship is, of course, simply butlast. Here is the procedure that results from this process of generalization:

to downup :word
print :word
downup butlast :word
print :word
end

As you already know, this procedure won't quite work. It lacks a stop rule. But once we have come this far, it's a relatively simple matter to add the stop rule. All we have to do is ask ourselves, "What's the smallest case we want the program to handle?" The answer is that for a single-letter word the downup should just print the word once. In other words, for a single-letter word, downup should carry out its first instruction and then stop. So the stop rule goes after that first instruction, and it stops if the input has only one letter:

to downup :word
print :word
if equalp count :word 1 [stop]
downup butlast :word
print :word
end

Voilà!

The trick is not to think about the stop rule at first. Just accept, on faith, that the procedure will somehow manage to work for inputs that are smaller than the one you're interested in. Most people find it hard to do that. Since you haven't written the program yet, after all, the faith I'm asking you to show is really unjustified. Nevertheless you have to pretend that someone has already written a version of the desired procedure that works for smaller inputs.

Let's take another example from Chapter 7.

? one.per.line "hello
h
e
l
l
o

There are two different ways in which we can find a smaller pattern within this one. First we might notice this one:

one.per.line results

This pattern would lead to the following procedure, for which I haven't yet invented a stop rule.

to one.per.line :word
print first :word
one.per.line butfirst :word
end

Alternatively we might notice this pattern:

alternate one.per.line view

In that case we'd have a different version of the procedure. This one, also, doesn't yet have a stop rule.

to one.per.line :word
one.per.line butlast :word
print last :word
end

Either of these procedures can be made to work by adding the appropriate stop rule:

if emptyp :word [stop]

This instruction should be the first in either procedure. Since both versions work, is there any reason to choose one over the other? Well, there's no theoretical reason but there is a practical one. It turns out that first and butfirst work faster than last and butlast. It also turns out that procedures that are tail recursive (that is, with the recursion step at the end) can survive more levels of invocation, without running out of memory, than those that are recursive in other ways. For both of these reasons the first version of one.per.line is a better choice than the second. (Try timing both versions with a very long list as input.)

»Rewrite the say procedure from Chapter 5 recursively.

The Leap of Faith

If we think of

to one.per.line :word
print first :word
one.per.line butfirst :word
end

merely as a statement of a true fact about the "shape" of the result printed by one.per.line, it's not very remarkable. The amazing part is that this fragment is runnable!* It doesn't look runnable because it invokes itself as a helper procedure, and--if you haven't already been through the combining method--that looks as if it can't work. "How can you use one.per.line when you haven't written it yet?"

*Well, almost. It needs a base case.

The leap of faith method is the assumption that the procedure we're in the middle of writing already works. That is, if we're thinking about writing a one.per.line procedure that can compute one.per.line "hello, we assume that one.per.line "ello will work.

Of course it's not really a leap of faith, in the sense of something accepted as miraculous but not understood. The assumption is justified by our understanding of the combining method. For example, we understand that the five-letter one.per.line is relying on the four-letter version of the problem, not really on itself, so there's no circular reasoning involved. And we know that if we had to, we could write one.per.line1 through one.per.line4 "by hand."

The reason that the technique in this chapter may seem more mysterious than the combining method is that this time we are thinking about the problem top-down. In the combining method, we had already written whatever4 before we even raised the question of whatever5. Now we start by thinking about the larger problem and assume that we can rely on the smaller one. Again, we're entitled to that assumption because we've gone through the process from smaller to larger so many times already.

The leap of faith method, once you understand it, is faster than the combining method for writing new recursive procedures, because you can write the recursive solution immediately, without bothering with many individual cases. The reason I showed you the combining method first is that the leap of faith method seems too much like magic, or like "cheating," until you've seen several believable recursive programs. The combining method is the way to learn about recursion; the leap of faith method is the way to write recursive procedures once you've learned.

The Tower of Hanoi

One of the most famous recursive problems is a puzzle called the Tower of Hanoi. You can find this puzzle in toy stores; look for a set of three posts and five or six disks. You start out with the puzzle arranged like this:

figure: hanoi1

The object of the puzzle is to move all of the disks to the second post, like this:

figure: hanoi2

This looks easy, but there are rules you must follow. You can only move one disk at a time, and you can't put a disk on top of a smaller disk. You might start trying to solve the puzzle this way:

figure: hanoi3

After that, you could move disk number 1 either onto post A, on top of disk 3, or onto post C, on top of disk 2.

I'm about to describe a solution to the puzzle, so if you want to work on it yourself first, stop reading now.

In the examples of downup and one.per.line, we identified each problem as one for which a recursive program was appropriate because within the pattern of the overall solution we found a smaller, similar pattern. The same principle will apply in this case. We want to end up with all five disks on post B. To do that, at some point we have to move disk 5 from post A to post B. To do that, we first have to get the other four disks out of the way. Specifically, "out of the way" must mean onto post C. So the solution to the problem can be represented graphically this way, in three parts:

figure: hanoi4

The first part of the solution is to move disks 1 through 4 from post A to post C. The second part is a single step, moving disk 5 from post A to post B. The third part, like the first, involves several steps, to move disks 1 through 4 from post C to post B.

If you've developed the proper recursive spirit, you'll now say, "Aha! The first part and the third part are just like the entire puzzle, only with four disks instead of five!" I hope that after this example you'll develop a sort of instinct that will let you notice patterns like that instantly. You should then be ready to make a rough draft of a procedure to solve the puzzle:

to hanoi :number
hanoi :number-1
movedisk :number
hanoi :number-1
end

Of course, this isn't at all a finished program. For one thing, it lacks a stop rule. (As usual, we leave that part for last.) For another, we have to write the subprocedure movedisk that moves a single disk. But a more important point is that we've only provided for changing the disk number we're moving, not for selecting which posts to move from and to. You might want to supply hanoi with two more inputs, named from and to, which would be the names of the posts. So to solve the puzzle we'd say

hanoi 5 "A "B

But that's not quite adequate. Hanoi also needs to know the name of the third post. Why? Because in the recursive calls, that third post becomes one of the two "active" ones. For example, here are the three steps in solving the five-disk puzzle:

hanoi 4 "A "C
movedisk 5 "A "B
hanoi 4 "C "B

You can see that both of the recursive invocations need to use the name of the third post. Therefore, we'll give hanoi a fourth input, called other, that will contain that name. Here is another not-quite-finished version:

to hanoi :number :from :to :other
hanoi :number-1 :from :other :to
movedisk :number :from :to
hanoi :number-1 :other :to :from
end

This version still lacks a stop rule, and we still have to write movedisk. But we're much closer. Notice that movedisk does not need the name of the third post as an input. Its job is to take a single step, moving a single disk. The unused post really has nothing to do with it. Here's a simple version of movedisk:

to movedisk :number :from :to
print (sentence [Move disk] :number "from :from "to :to)
end

What about the stop rule in hanoi? The first thing that will come to your mind, probably, is that the case of moving disk number 1 is special because there are no preconditions. (No other disk can ever be on top of number 1, which is the smallest.) So you might want to use this stop rule:

if equalp :number 1 [movedisk 1 :from :to stop]

Indeed, that will work. (Where would you put it in the procedure?) But it turns out that a slightly more elegant solution is possible. You can let the procedure for disk 1 go ahead and invoke itself recursively for disk number 0. Since there is no such disk, the procedure then has nothing to do. By this reasoning the stop rule should be this:

if equalp :number 0 [stop]

You may have to trace out the procedure to convince yourself that this really works. Convincing yourself is worth the effort, though; it turns out that very often you can get away with allowing an "extra" level of recursive invocation that does nothing. When that's possible, it makes for a very clean-looking procedure. (Once again, I've left you on your own in deciding where to insert this stop rule in hanoi.)

If your procedure is working correctly, you should get results like this for a small version of the puzzle:

? hanoi 3 "A "B "C
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B

If you like graphics programming and have been impatient to see a turtle in this book, you might want to write a graphic version of movedisk that would actually display the moves on the screen.

More Complicated Patterns

Suppose that, instead of downup, we wanted to write updown, which works like this:

? updown "hello
h
he
hel
hell
hello
hell
hel
he
h

It's harder to find a smaller subproblem within this pattern. With downup, removing the first and last lines of the printout left a downup pattern for a shorter word. But the middle lines of this updown pattern aren't an updown. The middle lines don't start with a single letter, like the h in the full pattern. Also, the middle lines are clearly made out of the word hello, not some shortened version of it. » You might want to try to find a solution yourself before reading further.

There are several approaches to writing updown. One thing we could do is to divide the pattern into two parts:

up and down

It is relatively easy to invent the procedures up and down to create the two parts of the pattern.

to up :word
if emptyp :word [stop]
up butlast :word
print :word
end

to down :word
if emptyp :word [stop]
print :word
down butlast :word
end

Then we can use these as subprocedures of the complete updown:

to updown :word
up :word
down butlast :word
end

Another approach would be to use numbers to keep track of things, as in the inout example of Chapter 7. In this case we can consider the middle lines as a smaller version of the problem.

nested updowns

In this point of view all the inner, smaller updown patterns are made from the same word, hello. But each invocation of updown1 (which is what I'll call this version of updown) will use a second input, a number that tells it how many letters to print in the first and last lines:

? updown1 "hello 3
hel
hell
hello
hell
hel
? updown1 "hello 5
hello

We need a subprocedure, truncate, that prints the beginning of a word, up to a certain number of letters.

to truncate :word :size
if equalp count :word :size [print :word stop]
truncate butlast :word :size
end

to updown1 :word :size
truncate :word :size
if equalp count :word :size [stop]
updown1 :word :size+1
truncate :word :size
end

(The helper procedure truncate is the sort of thing that should really be an operation, for the same reason that second was better than prsecond here. We'll come back to the writing of recursive operations in Chapter 11.)

Finally, we can write a new superprocedure called updown that uses updown1 with the correct inputs. (If you try all these approaches on the computer, remember that you can have only one procedure named updown in your workspace at a time.)

to updown :word
updown1 :word 1
end

A third approach, which illustrates a very powerful technique, also uses an initialization procedure updown and a subprocedure updown1 with two inputs. In this version, though, both inputs to the subprocedure are words: the partial word that we're printing right now and the partial word that is not yet to be printed.

alternate updowns

In this example, to print an updown pattern for the word hello, the two subprocedure inputs would be h (what's printed on the first line) and ello (what isn't printed there). For the inner pattern with the first and last lines removed, the two inputs would be he and llo. Here is the program:

to updown1 :now :later
print :now
if emptyp :later [stop]
updown1 (word :now first :later) butfirst :later
print :now
end

to updown :word
updown1 first :word butfirst :word
end

This program may be a little tricky to understand. The important part is updown1. Read it first without paying attention to the stop rule; see if you can understand how it corresponds to the updown pattern. A trace of its recursive invocations might help:

updown "hello
  updown1 "h "ello
    updown1 "he "llo
      updown1 "hel "lo
        updown1 "hell "o
          updown1 "hello "

The innermost level of recursion has been reached when the second input is the empty word. Notice how first, butfirst, and word are used in combination to calculate the inputs.

»Write a recursive procedure slant that takes a word as input and prints it on a diagonal, one letter per line, like this:

? slant "salami
s
 a
  l
   a
    m
     i

A Mini-project: Scrambled Sentences

Just as Logo programs can be iterative or recursive, so can English sentences. People are pretty good at understanding even rather long iterative sentences: "This is the farmer who kept the cock that waked the priest that married the man that kissed the maiden that milked the cow that tossed the dog that worried the cat that killed the rat that ate the malt that lay in the house that Jack built." But even a short recursive (nested) sentence is confusing: "This is the rat the cat the dog worried killed."

»Write a procedure that takes as its first input a list of noun-verb pairs representing actor and action, and as its second input a word representing the object of the last action in the list. Your procedure will print two sentences describing the events, an iterative one and a nested one, following this pattern:

? scramble [[girl saw] [boy owned] [dog chased] [cat bit]] "rat
This is
the girl that saw
the boy that owned
the dog that chased
the cat that bit
the rat

This is
the rat
the cat
the dog
the boy
the girl
saw
owned
chased
bit

You don't have to worry about special cases like "that Jack built"; your sentences will follow this pattern exactly.

Ordinarily the most natural way to program this problem would be as an operation that outputs the desired sentence, but right now we are concentrating on recursive commands, so you'll write a procedure that prints each line as shown above.

Procedure Patterns

Certain patterns come up over and over in programming problems. It's worth your while to learn to recognize some of them. For example, let's look again at one.per.line:

to one.per.line :word
if emptyp :word [stop]
print first :word
one.per.line butfirst :word
end

This is an example of a very common pattern:

to procedure :input
if emptyp :input [stop]
do.something.to first :input
procedure butfirst :input
end

A procedure pattern is different from the result patterns we examined earlier in this chapter. Before we were looking at what we wanted a not-yet-written procedure to accomplish; now we are looking at already-written procedures to find patterns in their instructions. A particular procedure might look like this pattern with the blanks filled in. Here's an example:

to praise :flavors
if emptyp :flavors [stop]
print sentence [I love] first :flavors
praise butfirst :flavors
end

? praise [[ultra chocolate] [chocolate cinnamon raisin] ginger]
I love ultra chocolate
I love chocolate cinnamon raisin
I love ginger

Do you see how praise fits the pattern?

»Continuing our investigation of literary forms, write a procedure to compose love poems, like this:

? lovepoem "Mary
M is for marvelous, that's what you are.
A is for awesome, the best by far.
R is for rosy, just like your cheek.
Y is for youthful, with zest at its peak.
Put them together, they spell Mary,
The greatest girl in the world.

The core of this project is a database of deathless lines, in the form of a list of lists:

make "lines [[A is for albatross, around my neck.]
             [B is for baloney, your opinions are dreck.]
             [C is for corpulent, ...] ...]

and a recursive procedure select that takes a letter and a list of lines as inputs and finds the appropriate line to print by comparing the letter to the beginning of each line in the list.

Another common pattern is a recursive procedure that counts something numerically, like countdown:

to countdown :number
if equalp :number 0 [stop]
print :number
countdown :number-1
end

And here is the pattern:

to procedure :number
if equalp :number 0 [stop]
do.something
procedure :number-1
end

A procedure built on this pattern is likely to have additional inputs so that it can do something other than just manipulate the number itself. For example:

to manyprint :number :text
if equalp :number 0 [stop]
print :text
manyprint :number-1 :text
end

? manyprint 4 [Lots of echo in this cavern.]
Lots of echo in this cavern.
Lots of echo in this cavern.
Lots of echo in this cavern.
Lots of echo in this cavern.

to multiply :letters :number
if equalp :number 0 [stop]
print :letters
multiply (word :letters first :letters) :number-1
end

? multiply "f 5
f
ff
fff
ffff
fffff

One way to become a skillful programmer is to study other people's programs carefully. As you read the programs in this book and others, keep an eye open for examples of patterns that you think might come in handy later on.

Tricky Stop Rules

Suppose that instead of one.per.line we'd like a procedure to print the members of a list two per line. (This is plausible if we have a list of many short items, for example. We'd probably want to control the spacing on each line so that the items would form two columns, but let's not worry about that yet.)

The recursive part of this program is fairly straightforward:

to two.per.line :stuff
print list (first :stuff) (first butfirst :stuff)
two.per.line butfirst butfirst :stuff
end

The only thing out of the ordinary is that the recursive step uses a subproblem that's smaller by two members, instead of the usual one.

But it's easy to fall into a trap about the stop rule. It's not good enough to say

if emptyp :stuff [stop]

because in this procedure it matters whether the length of the input is odd or even. These two possibilities give rise to two stop rules. For an even-length list, we stop if the input is empty. But for an odd-length list, we must treat the case of a one-member list specially also.

to two.per.line :stuff
if emptyp :stuff [stop]
if emptyp butfirst :stuff [show first :stuff stop]
print list (first :stuff) (first butfirst :stuff)
two.per.line butfirst butfirst :stuff
end

It's important to get the two stop rules in the right order; we must be sure the input isn't empty before we try to take its butfirst.

»Why does this procedure include one show instruction and one print instruction? Why aren't they either both show or both print?

(back to Table of Contents)

BACK chapter thread NEXT

Brian Harvey, bh@cs.berkeley.edu