Metamagical Themas, page 54
Let me give a simple example based on this silly riddle: "How do you make a pile of 13 stones?" Answer: "Put one stone on top of a pile of 12 stones." (Ask a silly question and get an answer 12/13 as silly.) Suppose we want to make a Lisp function that will give us not a pile of 13 stones, but a list consisting of 13 copies of the atom stone-or in general, n copies of that atom. We can base our answer on the riddle's silly-seeming yet correct recursive answer. The general notion is to build the answer for n out of the answer for n's predecessor. Build how? Using the list-building function cons, that's how. What's the embryonic case? That is, for which value of
• does this riddle present absolutely no problem at all? That's easy: when
• equals 0, our list should be empty, which means the answer is nil. We can now put our observations together as follows:
(def bunch-of-stones (lambda (n
(cond ((eq n 0) nil)
(t (cons 'stone (bunch-of-stones (next-smaller n)))))))
Now let's watch the genie put together a very small bunch of stones (with trace on, just for fun):
-> (bunch-of-stones 2)
ENTERING bunch-of-stones (n=2)
ENTERING bunch-of-stones (n=1)
ENTERING bunch-of-stones (n=0)
EXITING bunch-of-stones (value: nil)
EXITING bunch-of-stones (value: (stone))
EXITING bunch-of-stones (value: (stone stone))
(stone stone)
->
This is what is called "consing up a list". Now let's try another one. This one is an old chestnut of Lisp and indeed of recursion in general. Look at the definition and see if you can figure out what it's supposed to do; then read on to see if you were right.
-> (def wow (lambda (n)
(cond ((eq n 0) 1)
(t (times n (wow (subs n)))))))
Remember, subl means the same as next-smaller. For a lark, why don't you calculate the value of (wow 100)? (If you ate your mental Wheaties this morning, try it in your head.)
It happens that Lisp genies often mumble out loud while they are executing wishes, and I just happen to have overheard this one as it was executing the wish (wow 100). Its soliloquy ran something like this:
Hmm ... (wow 100), eh? Well, 100 surely isn't equal to 0, so I guess the answer has to be 100 times what it would have been, had the problem been (wow 99). All rightie-now all I need to do is figure out what (wow 99) is. Oh, this is going to be a piece of cake! Let's see, is 99 equal to 0? No, seems not to be, so I guess the answer to this problem must be 99 times what the answer would have been, had the problem been (wow 98). Oh, this is going to be child's play! Let's see ...
At this point, the author, having some pressing business at the bank, had to leave the happy genie, and did not again pass the spot until some milliseconds afterwards. When he did so, the genie was just finishing up, saying:
... And now I just need to multiply that by 100, and I've got my final answer.
Easy as pie! I believe it comes out to be
93326215443944152681699238
85626670049071596826438162146859296389521759999322991560894146
39761565182862536979208272237582511852109168640000000000000000
00000000-if I'm not mistaken.
Is that the answer you got, dear reader? No? Ohhh, I see where you went wrong. It was in your multiplication by 52. Go back and try it again from that point on, and be a little more careful in adding those long columns up. I'm quite sure you'll get it right this time.
* * *
This wow function is ordinarily called factorial,- n factorial is usually defined to be the product of all the numbers from 1 through n. But a recursive definition looks at things slightly differently: speaking recursively, n factorial is simply the product of n and the previous factorial. It reduces the given problem to a simpler sort of the same type. That simpler one will in turn be reduced, and so on down the line, until you come to the simplest problem of that type, which I call the "embryonic case" or the "bottom line". People often speak, in fact, of a recursion "bottoming out".
A New Yorker cartoon from a few years back illustrates the concept perfectly. It shows a fifty-ish man holding a photograph of himself roughly ten years earlier. In that photograph, he is likewise holding a photograph of himself, ten years earlier than that. And on it goes, until eventually it "bottoms out"-quite literally-in a photograph of a bouncy baby boy in his birthday suit (bottom in the air). This idea of recursive photos catching you as you grow up is quite appealing. I wish my parents had thought of it!
Contrast it with the more famous Morton Salt infinite regress, in which the Morton Salt girl holds a box of Morton Salt with her picture on it-but as the girl in the picture is no younger, there is no bottom line and the regress is endless, at least theoretically. Incidentally, the Dutch cocoa called "Droste's" has a similar illustration on its boxes, and very likely so do some ,other products.
The recursive approach works when you have a family of related problems, at least one of which is so simple that it can be answered immediately. This I call the embryonic case. (In the factorial example, that's the (eq n 0) case, whose answer is 1.) Each problem ("What is 100 factorial?", for instance) can be viewed as a particular case of one general problem ("How do you calculate factorials?"). Recursion takes advantage of the fact that the answers to various cases are related in some logical way to each other. (For example, I could very easily tell you the value of 100 factorial if only somebody would hand me the value of 99 factorial-all I need to do is multiply by 100.) You could say that the "Recursioneer's Motto" is: "Gee, I could solve this case if only someone would magically hand me the answer to the case that's one step closer to the embryonic case." Of course, this motto presumes that certain cases are, in some sense, "nearer" to the embryonic case than others are-in fact, it presumes that there is a natural pathway leading from any case through simpler cases all the way down to the embryonic case, a pathway whose steps are clearly marked all along the way.
As it turns out, this is a very reasonable assumption to make in all sorts of circumstances. To spell out the exact nature of this recursion-guiding pathway, you have to answer two Big Questions:
(1) What is the embryonic case?
(2) What is the relationship of a typical case to the next simpler case?
Now actually, both of these Big Questions break up into two subquestions (as befits any self-respecting recursive question!), one concerning how you recognize where you are or how to move, the other concerning what the answer is at any given stage. Thus, spelled out more explicitly, our Big Questions are:
(la) How can you know when you've reached the embryonic case? (lb) What is the embryonic answer?
(2a) From a typical case, how do you take exactly one step toward the embryonic case?
(2b) How do you build this case's answer out of the "magically given" answer to the simpler case?
' Question (2a) concerns the nature of the descent toward the embryonic case, or bottom line. Question (2b) concerns the inverse aspect, namely, the ascent that carries you back up from the bottom to the top level. In the case of the factorial, the answers to the Big Questions are:
(1a) The embryonic case occurs when the argument is 0.
(lb) The embryonic answer is 1.
(2a) Subtract 1 from the present argument.
(2b) Multiply the "magic" answer by the present argument.
Notice how the answers to these four questions are all neatly incorporated in the recursive definition of wow.
* * *
Recursion relies on the assumption that sooner or later you will bottom out. One way to be sure you'll bottom out is to have all the simplifying or "descending" steps move in the same direction at the same rate, so that your pathway is quite obviously linear. For instance, it's obvious that by subtracting 1 over and over again, you will eventually reach 0, provided you started with a positive integer. Likewise, it's obvious that by performing the list-shortening operation of cdr, you will eventually reach nil, provided you started with a finite list. For this reason, recursions using SUM or cdr to define their pathway of descent toward the bottom are commonplace. I'll show a cdr-based recursion shortly, but first I want to show a funny numerical recursion in which the pathway toward the embryonic case is anything but linear and smooth. In fact, it is so much like a twisty mountain road that to describe it as moving "towards the embryonic case" seems hardly accurate. And yet, just as mountain roads, no matter how many hairpin turns they make, eventually do hit their destinations, so does this path.
Consider the famous "3n -f 1" problem, in which you start with any positive integer, and if it is even, you halve it; otherwise, you multiply it by 3 and add 1. Let's call the result of this operation on n (hotpo n) (standing for "half or triple plus one"). Here is a Lisp definition of hotpo:
(def hotpo (lambda (n)
(cond ((even n) (half n))
(t (addl (times 3 n))))))
This definition presumes that two other functions either have been or will be defined elsewhere for the Lisp genie, namely even and half (addl and times being, as mentioned earlier, intrinsic parts of Lisp). Here are the lacking definitions:
(def even (lambda (n) (eq (remainder n 2) 0)))
(def half (lambda (n) (quotient n 2)))
What do you think happens if you begin with some integer and perform hotpo over and over again? Take 7, for instance, as your starting point. Before you do the arithmetic, take a guess as to what sort of behavior might occur.
As it turns out, the pathway followed is often surprisingly chaotic and bumpy. For instance, if we begin with 7, the process leads us to 22, then 11, then 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1.... Note that we have wound up in a short loop (a 3-cycle, in the terminology of Chapter 16). Suppose we therefore agree that if we ever reach 1, we have "hit bottom" and may stop. You might well ask, "Who says we will hit 1? Is there a guarantee?" (Again in the terminology of Chapter 16, we could ask, "Is the 1-4-2-1 cycle an attractor?") Indeed, before you try it out in a number of cases, you have no particular reason to suspect that you will ever hit 1, let alone always. (It would be very surprising if someone correctly anticipated what would happen in the case of, say, 7 before trying it out.) However, numerical experimentation reveals a remarkable reliability to the process; it seems that no matter where you start, you always do enter the 1-4-2-1 cycle sooner or later. (Try starting with 27 as seed if you want a real roller-coaster ride!)
Can you write a recursive function to reveal the pathway followed from an arbitrary starting point "down" to 1? Note that I say "down" advisedly, since many of the steps are in fact up! Thus the pathway starting at 3 would be the list (3 10 5 16 8 4 2 1). In order to solve this puzzle, you need to go back and answer for yourself the two Big Questions of Recursion, as they apply here. Note:
(cond ((not (want help)) (not (read further)))
(t (read further)))
* * *
First-about the embryonic case. This is easy. It has already been defined as the arrival at 1; and the embryonic, or simplest possible, answer is the list (1), a tiny but valid pathway from 1 to 1.
Second-about the more typical cases. What operation will carry us from typical 7 one step closer to embryonic 1? Certainly not the subl operation. No-by definition it's the function hotpo itself that brings you ever "nearer" to 1-even when it carries you up! This teasing quality is of course the whole point of the example. What about (2b)-how to recursively build a list documenting our wildly oscillating pathway? Well, the pathway belonging to 7 is gotten by tacking (i.e., consing) 7 onto the shorter pathway belonging to (hotpo 7), or 22. After all, 22 is one step closer to being embryonic than 7 is!
These answers enable us to write down the desired function definition, using tato as our dummy variable (tato being a well-known acronym for tato (and tato only), which recursively expands to tato (and tato only) (and tato (and tato only) only)-and so forth).
(def pathway-to-1 (lambda (tato)
(cond ((eq tato 1) '(1))
(t (cons tato (pathway-to-1 (hotpo tato)))))))
Look at the way the Lisp genie "thinks" (as revealed when the trace feature is on):
-> (pathway-to-i 3)
ENTERING pathway-to-i (tato=3)
ENTERING pathway-to-1 (tato=10)
ENTERING pathway-to-1 (tato=5)
ENTERING pathway-to-1 (tato=16)
ENTERING pathway-to-1 (tato=8)
ENTERING pathway-to-i (tato=4)
ENTERING pathway-tai (tato=2)
ENTERING pathway-to-1 (tato=1)
EXITING pathway-to-1 (value: (1))
EXITING pathway-to-1 (value: (2 1))
EXITING pathway-to-i (value: (4 2 1))
EXITING pathway-to-1 (value: (8 4 2 1))
EXITING pathway-to-1 (value: (16 8 4 2 1))
EXITING pathway-to-1 (value: (5 16 8 4 2 1))
EXITING pathway-to-1 (value: (10 5 16 8 4 2 1))
EXITING pathway-to-1 (value: (3 10 5 16 8 4 2 1))
(3 10 5 16 8 4 2 1)
->
Notice the total regularity (the sideways `V' shape) of the left margin of the trace diagram, despite the chaos of the numbers involved. Not all recursions are so geometrically pretty, when traced. This is because some problems request more than one subproblem to be solved. As a practical real-life example of such a problem, consider how you might go about counting up all the unicorns in Europe. This is certainly a nontrivial undertaking, yet there is an elegant recursive answer: Count up all the unicorns in Portugal, also count up all the unicorns in the other 30-odd countries of Europe, and finally add those two results together.
Notice how this spawns two smaller unicorn-counting subproblems, which in turn will spawn two subproblems each, and so on. Thus, how can one count all the unicorns in Portugal? Easy: Add the number of unicorns in the Estremadura region to the number of unicorns in the rest of Portugal! And how do you count up the unicorns in Estremadura (not to mention those in the remaining regions of Portugal)? By further breakup, of course.
But what is the bottom line? Well, regions can be broken up into districts,
districts into square kilometers, square kilometers into hectares, hectares into square meters-and presumably we can handle each square meter without further breakup.
Although this may sound rather arduous, there really is no other way to conduct a thorough census than to traverse every single part on every level of the full structure that you have, no matter how giant it may be. There is a perfect Lisp counterpart to this unicorn census: it is the problem of determining how many atoms there are inside an arbitrary list. How can we write a Lisp function called atomcount that will give us the answer 15 when it is shown the following strange-looking list (which we'll call brahma)?
(((ac ab cb) ac (ba be ac)) ab ((cb ca ba) cb (ac ab cb)))
One method, expressed recursively, is exactly parallel to that for ascertaining the unicorn population of Europe. See if you can come up with it on your own.
* * *
The idea is this. We want to construct the answer-namely, 15-out of the answers to simpler atom-counting problems. Well, it is obvious that one simpler atom-counting problem than (atomcount brahma) is (atomcount (car brahma)). Another one is (atomcount (cdr brahma)). The answers to these two problems are, respectively, 7 and 8. Now clearly, 15 is made out of 7 and 8 by addition-which makes sense, after all, since the total number of atoms must be the number in the car plus the number in the cdr. There's nowhere else for any atoms to hide! Well, this analysis gives us the following recursive definition, with s as the dummy variable:
(def atomcount (lambda (s)
(plus (atomcount (car s)) (atomcount (cdr s)))))
It looks very simple, but it has a couple of flaws. First, we have written the recursive part of the definition, but we have utterly forgotten the other equally vital half-the "bottom line". It reminds me of the Maryland judge I once read about in the paper, who ruled: "A horse is a four-legged animal that is produced by two other horses." This is a lovely definition, but where does it bottom out? Similarly for atomcount. What is the simplest case, the embryonic case, of atomcount? Simple: It is when we are asked to count the atoms in a single atom. The answer, in such a case, is of course 1. But how can we know when we are looking at an atom? Fortunately, Lisp has a built-in function called atom that returns t (meaning "true") whenever we are looking at an atom, and nil otherwise. Thus (atom 'plop) returns t, while (atom '(a b c)) returns nil. Using that, we can patch up our definition:
(def atomcount (lambda (s)
(cond ((atom s) 1)
(t (plus (atomcount (car s)) (atomcount (cdr s)))))))
Still, though, it is not quite right. If we ask the genie for atomcount of (a b c), instead of getting 3 for an answer, we will get 4. Shocking! How come this happens? Well, we can pin the problem down by trying an even simpler example: if we ask for (atomcount '(a)), we find we get 2 instead of 1. Now the error should be clearer: 2 =1 + 1, with 1 each coming from the car and cdr of (a). The car is the atom a which indeed should be counted as 1, but the cdr is nil, which should not. So why does nil give an atomcount of 1? Because nil is not only an empty list, it is also an atom! To suppress this bad effect, we simply insert another cond clause at the very top:
(def atomcount (lambda (s)
(cond ((null s) 0)
((atom s) 1)
(t (plus (atomcount (car s)) (atomcount (cdr s)))))))
