diff options
| author | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
| commit | 562a9a52d599d9a05f871404050968a5fd282640 (patch) | |
| tree | 7d3305c1252c043bfe246ccc7deff0056aa6b5ab /js/games/nluqo.github.io/~bh/v1ch8/v1ch8.html | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/v1ch8/v1ch8.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch8/v1ch8.html | 756 |
1 files changed, 756 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/v1ch8/v1ch8.html b/js/games/nluqo.github.io/~bh/v1ch8/v1ch8.html new file mode 100644 index 0000000..df14a95 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch8/v1ch8.html @@ -0,0 +1,756 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 1 ch 8: Practical Recursion: the Leap of Faith</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 1: +<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT +<H1>Practical Recursion: the Leap of Faith</H1> + +<TABLE width="100%"><TR><TD> +<IMG SRC="../csls1.jpg" ALT="cover photo"> +<TD><TABLE> +<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian +Harvey</A><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><BR> +<TR><TD align="right"><A HREF="../pdf/v1ch08.pdf">Download PDF version</A> +<TR><TD align="right"><A HREF="../v1-toc2.html">Back to Table of Contents</A> +<TR><TD align="right"><A HREF="../v1ch7/v1ch7.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch9/v1ch9.html"><STRONG>NEXT</STRONG></A> +<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-1">MIT +Press web page for Computer Science Logo Style</A> +</TABLE></TABLE> + +<HR> + +<P> +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 <CODE>downup5</CODE> to rely on +<CODE>downup4</CODE>. + +<P>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. + +<P> +<H2>Recursive Patterns</H2> + +<P> +Let's look, once more, at the problem we were trying to solve when +writing the <CODE>downup</CODE> procedure. We wanted the program to behave +like this: + +<PRE>? <U>downup "hello</U> +hello +hell +hel +he +h +he +hel +hell +hello +</PRE> + +<P>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 +<CODE>downup</CODE> this way: +<P><CENTER><IMG SRC="recur2-1.gif" ALT="downup hello results"></CENTER> +<P>What I've done here is to notice that the printout from applying <CODE> +downup</CODE> to a five-letter word, <CODE>hello</CODE>, includes within itself the +printout that would result from applying <CODE>downup</CODE> to a smaller +word, <CODE>hell</CODE>. + +<P>This is where the leap of faith comes in. I'm going to pretend that +<CODE>downup</CODE> <EM>already works</EM> 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 +<PRE>downup "hello +</PRE> + +<P>we must carry out these three instructions: +<PRE>print "hello +downup "hell +print "hello +</PRE> + +<P>(The two <CODE>print</CODE> instructions print the first and last +lines of the desired result, the ones that aren't part of the smaller +<CODE>downup</CODE> printout.) + +<P>To turn these instructions into a general procedure, we must use a +variable in place of the specific word <CODE>hello</CODE>. We also have to +figure out the general relationship that is exemplified by the +transformation from <CODE>hello</CODE> into <CODE>hell</CODE>. This relationship +is, of course, simply <CODE>butlast</CODE>. Here is the procedure that +results from this process of generalization: +<PRE>to downup :word +print :word +downup butlast :word +print :word +end +</PRE> + +<P>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 <CODE>downup</CODE> should just print the word +once. In other words, for a single-letter word, <CODE>downup</CODE> 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: +<PRE>to downup :word +print :word +if equalp count :word 1 [stop] +downup butlast :word +print :word +end +</PRE> + +<P>Voilà! + +<P>The trick is <EM>not</EM> 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. + +<P>Let's take another example from Chapter 7. +<PRE>? <U>one.per.line "hello</U> +h +e +l +l +o +</PRE> + +<P>There are two different ways in which we can find a smaller pattern +within this one. First we might notice this one: +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch8/recur2-2.gif" ALT="one.per.line results"></CENTER> +<P>This pattern would lead to the following procedure, for +which I haven't yet invented a stop rule. + +<P><PRE>to one.per.line :word +print first :word +one.per.line butfirst :word +end +</PRE> + +<P>Alternatively we might notice this pattern: +<P><CENTER><IMG SRC="recur2-3.gif" ALT="alternate one.per.line view"></CENTER> +<P>In that case we'd have a different version of the +procedure. This one, also, doesn't yet have a stop rule. + +<P><PRE>to one.per.line :word +one.per.line butlast :word +print last :word +end +</PRE> + +<P>Either of these procedures can be made to work by adding the +appropriate stop rule: +<PRE>if emptyp :word [stop] +</PRE> + +<P>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 <CODE>first</CODE> and <CODE>butfirst</CODE> work faster +than <CODE>last</CODE> and <CODE>butlast</CODE>. 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 <CODE>one.per.line</CODE> is a better +choice than the second. (Try timing both versions with a very long +list as input.) + +<P>»Rewrite <A HREF="../v1ch5/hof.html#say">the <CODE>say</CODE> procedure</A> +from Chapter 5 recursively. + + +<P><H2>The Leap of Faith</H2> + +<P>If we think of + +<P><PRE>to one.per.line :word +print first :word +one.per.line butfirst :word +end +</PRE> + +<P>merely as a statement of a true fact +about the "shape" of the result printed by +<CODE>one.per.line</CODE>, it's not very remarkable. The amazing part is that +this fragment is <EM>runnable!</EM><SUP>*</SUP> It doesn't <EM>look</EM> 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 <CODE>one.per.line</CODE> +when you haven't written it yet?" + +<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>Well, almost. It needs a base +case.</SMALL></BLOCKQUOTE></SMALL><P>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 +<CODE>one.per.line</CODE> procedure that can compute <CODE>one.per.line "hello</CODE>, we +assume that <CODE>one.per.line "ello</CODE> will work. + +<P>Of course it's not <EM>really</EM> 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 <CODE>one.per.line</CODE> 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 <CODE>one.per.line1</CODE> through <CODE> +one.per.line4</CODE> "by hand." + +<P>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 <CODE>whatever4</CODE> +before we even raised the question of <CODE>whatever5</CODE>. 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. + +<P>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. + +<P><H2>The Tower of Hanoi</H2> + +<P>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: + +<P><CENTER><IMG SRC="hanoi1.gif" ALT="figure: hanoi1"></CENTER> + +<P>The object of the puzzle is to move all of the disks to the +second post, like this: + +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch8/hanoi2.gif" ALT="figure: hanoi2"></CENTER> + +<P>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: + +<P><CENTER><IMG SRC="hanoi3.gif" ALT="figure: hanoi3"></CENTER> + +<P>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. + +<P>I'm about to describe a solution to the puzzle, so if you want to work +on it yourself first, stop reading now. + +<P>In the examples of <CODE>downup</CODE> and <CODE>one.per.line</CODE>, 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 <EM>that,</EM> 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: + +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch8/hanoi4.gif" ALT="figure: hanoi4"></CENTER> + +<P>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. + +<P>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: + +<P><PRE>to hanoi :number +hanoi :number-1 +movedisk :number +hanoi :number-1 +end +</PRE> + +<P> +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 <CODE>movedisk</CODE> 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 <CODE>hanoi</CODE> with +two more inputs, named <CODE>from</CODE> and <CODE>to</CODE>, which would be the +names of the posts. So to solve the puzzle we'd say + +<P><PRE>hanoi 5 "A "B +</PRE> + +<P>But that's not quite adequate. <CODE>Hanoi</CODE> also needs to +know the name of the <EM>third</EM> 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: + +<P><PRE>hanoi 4 "A "C +movedisk 5 "A "B +hanoi 4 "C "B +</PRE> + +<P>You can see that both of the recursive invocations need to +use the name of the third post. Therefore, we'll give <CODE>hanoi</CODE> a +fourth input, called <CODE>other</CODE>, that will contain that name. Here +is another not-quite-finished version: + +<P><PRE>to hanoi :number :from :to :other +hanoi :number-1 :from :other :to +movedisk :number :from :to +hanoi :number-1 :other :to :from +end +</PRE> + +<P>This version still lacks a stop rule, and we still have to write <CODE> +movedisk</CODE>. But we're much closer. Notice that <CODE>movedisk</CODE> does <EM> +not</EM> 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 <CODE>movedisk</CODE>: + +<P><PRE>to movedisk :number :from :to +print (sentence [Move disk] :number "from :from "to :to) +end +</PRE> + +<P>What about the stop rule in <CODE>hanoi</CODE>? 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: + +<P><PRE>if equalp :number 1 [movedisk 1 :from :to stop] +</PRE> + +<P>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: + +<P><PRE>if equalp :number 0 [stop] +</PRE> + +<P>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 <CODE>hanoi</CODE>.) + +<P>If your procedure is working correctly, you should get +results like this for a small version of the puzzle: + +<P><PRE>? <U>hanoi 3 "A "B "C</U> +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 +</PRE> + +<P>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 <CODE> +movedisk</CODE> that would actually display the moves on the screen. + +<P><H2>More Complicated Patterns</H2> + +<P>Suppose that, instead of <CODE>downup</CODE>, we wanted to write <CODE> +updown</CODE>, which works like this: +<PRE>? <U>updown "hello</U> +h +he +hel +hell +hello +hell +hel +he +h +</PRE> + +<P>It's harder to find a smaller subproblem within this pattern. +With <CODE>downup</CODE>, removing the first and last lines of the printout left a +<CODE>downup</CODE> pattern for a shorter word. But the middle lines of this <CODE> +updown</CODE> pattern aren't an <CODE>updown</CODE>. The middle lines don't start with a +single letter, like the <CODE>h</CODE> in the full pattern. Also, the middle lines +are clearly made out of the word <CODE>hello</CODE>, not some shortened version of +it. » You might want to try to find a solution yourself before +reading further. + +<P>There are several approaches to writing <CODE>updown</CODE>. One thing we +could do is to divide the pattern into two parts: +<P><CENTER><IMG SRC="recur2-4.gif" ALT="up and down"></CENTER> +<P>It is relatively easy to invent the procedures <CODE>up</CODE> and +<CODE>down</CODE> to create the two parts of the pattern. +<PRE>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 +</PRE> + +<P>Then we can use these as subprocedures of the complete <CODE> +updown</CODE>: +<PRE>to updown :word +up :word +down butlast :word +end +</PRE> + +<P>Another approach would be to use numbers to keep track of things, as +in the <CODE>inout</CODE> example of Chapter 7. In this case we can +consider the middle lines as a smaller version of the problem. +<P><CENTER><IMG SRC="recur2-5.gif" ALT="nested updowns"></CENTER> +<P>In this point of view all the inner, smaller <CODE>updown</CODE> patterns +are made from the same word, <CODE>hello</CODE>. But each invocation of <CODE> +updown1</CODE> (which is what I'll call this version of <CODE>updown</CODE>) +will use a second input, a number that tells it how many +letters to print in the first and last lines: +<PRE>? <U>updown1 "hello 3</U> +hel +hell +hello +hell +hel +? <U>updown1 "hello 5</U> +hello +</PRE> + +<P>We need a subprocedure, <CODE>truncate</CODE>, that prints the +beginning of a word, up to a certain number of letters. +<PRE>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 +</PRE> + +<P>(The helper procedure <CODE>truncate</CODE> is the sort of thing that +should really be an operation, for the same reason that <CODE>second</CODE> was +better than <CODE>prsecond</CODE> <A HREF="../v1ch4/v1ch4.html#prsecond">here</A>. +We'll come back to the +writing of recursive operations in Chapter 11.) + +<P>Finally, we can write a new superprocedure called <CODE> +updown</CODE> that uses <CODE>updown1</CODE> with the correct inputs. (If you try +all these approaches on the computer, remember that you can have only +one procedure named <CODE>updown</CODE> in your workspace at a time.) +<PRE>to updown :word +updown1 :word 1 +end +</PRE> + +<P>A third approach, which illustrates a very powerful technique, also +uses an initialization procedure <CODE>updown</CODE> and a subprocedure <CODE> +updown1</CODE> 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. +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch8/recur2-6.gif" ALT="alternate updowns"></CENTER> +<P>In this +example, to print an <CODE>updown</CODE> pattern for the word <CODE>hello</CODE>, +the two subprocedure inputs would be <CODE>h</CODE> (what's printed on the +first line) and <CODE>ello</CODE> (what isn't printed there). For the inner +pattern with the first and last lines removed, the two inputs would be +<CODE>he</CODE> and <CODE>llo</CODE>. Here is the program: +<PRE>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 +</PRE> + +<P>This program may be a little tricky to understand. The +important part is <CODE>updown1</CODE>. Read it first without paying +attention to the stop rule; see if you can understand how it +corresponds to the <CODE>updown</CODE> pattern. A trace of its recursive invocations +might help: +<PRE>updown "hello + updown1 "h "ello + updown1 "he "llo + updown1 "hel "lo + updown1 "hell "o + updown1 "hello " +</PRE> + +<P>The innermost level of recursion has been reached when the second +input is the empty word. Notice how <CODE>first</CODE>, <CODE>butfirst</CODE>, and +<CODE>word</CODE> are used in combination to calculate the inputs. + +<P>»Write a recursive procedure <CODE>slant</CODE> that takes a word as input and +prints it on a diagonal, one letter per line, like this: + +<P><PRE>? <U>slant "salami</U> +s + a + l + a + m + i +</PRE> + +<P><H2>A Mini-project: Scrambled Sentences</H2> + +<P>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." + +<P>»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: + +<P><PRE>? <U>scramble [[girl saw] [boy owned] [dog chased] [cat bit]] "rat</U> +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 +</PRE> + +<P>You don't have to worry about special cases like "that Jack +built"; your sentences will follow this pattern exactly. + +<P>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 <CODE> +print</CODE>s each line as shown above. + +<P><H2>Procedure Patterns</H2> + +<P>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 <CODE>one.per.line</CODE>: + +<P><PRE>to one.per.line :word +if emptyp :word [stop] +print first :word +one.per.line butfirst :word +end +</PRE> + +<P>This is an example of a very common pattern: + +<P><PRE>to <U>procedure</U> :input +if emptyp :input [stop] +<U>do.something.to</U> first :input +<U>procedure</U> butfirst :input +end +</PRE> + +<P>A procedure pattern is different from the <EM>result</EM> 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: + +<P><PRE>to praise :flavors +if emptyp :flavors [stop] +print sentence [I love] first :flavors +praise butfirst :flavors +end + +? <U>praise [[ultra chocolate] [chocolate cinnamon raisin] ginger]</U> +I love ultra chocolate +I love chocolate cinnamon raisin +I love ginger +</PRE> + +<P>Do you see how <CODE>praise</CODE> fits the pattern? + +<P>»Continuing our investigation of literary forms, write a procedure to +compose love poems, like this: + +<P><PRE>? <U>lovepoem "Mary</U> +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. +</PRE> + +<P>The core of this project is a database of deathless lines, in the +form of a list of lists: + +<P><PRE>make "lines [[A is for albatross, around my neck.] + [B is for baloney, your opinions are dreck.] + [C is for corpulent, ...] ...] +</PRE> + +<P>and a recursive procedure <CODE>select</CODE> 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. + +<P>Another common pattern is a recursive procedure that counts something +numerically, like <CODE>countdown</CODE>: + +<P><PRE>to countdown :number +if equalp :number 0 [stop] +print :number +countdown :number-1 +end +</PRE> + +<P>And here is the pattern: + +<P><PRE>to <U>procedure</U> :number +if equalp :number 0 [stop] +<U>do.something</U> +<U>procedure</U> :number-1 +end +</PRE> + +<P>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: + +<P><PRE>to manyprint :number :text +if equalp :number 0 [stop] +print :text +manyprint :number-1 :text +end + +? <U>manyprint 4 [Lots of echo in this cavern.]</U> +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 + +? <U>multiply "f 5</U> +f +ff +fff +ffff +fffff +</PRE> + +<P>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. + +<P><H2>Tricky Stop Rules</H2> + +<P> +Suppose that instead of <CODE>one.per.line</CODE> we'd like a procedure to print +the members of a list <EM>two</EM> 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.) + +<P>The recursive part of this program is fairly straightforward: + +<P><PRE>to two.per.line :stuff +print list (first :stuff) (first butfirst :stuff) +two.per.line butfirst butfirst :stuff +end +</PRE> + +<P>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. + +<P>But it's easy to fall into a trap about the stop rule. It's not good enough +to say + +<P><PRE>if emptyp :stuff [stop] +</PRE> + +<P>because in this procedure it matters whether the length of the +input is odd or even. These two possibilities give rise to <EM>two</EM> 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. + +<P><PRE>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 +</PRE> + +<P>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 <CODE>butfirst</CODE>. + +<P>»Why does this procedure include one <CODE>show</CODE> instruction and one +<CODE>print</CODE> instruction? Why aren't they either both <CODE>show</CODE> or both +<CODE>print</CODE>? + +<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v1ch7/v1ch7.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch9/v1ch9.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |