1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
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>
|