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
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
|
<P>
<P><A NAME="gallery"></A><CENTER><IMG SRC="../ss-pics/gallery.jpg" ALT="figure: gallery"></CENTER><P><CENTER><EM>Print Gallery,</EM> by M. C. Escher (lithograph,
1956)
</CENTER><P>
<HTML>
<HEAD>
<TITLE>Simply Scheme: Introducing Computer Science ch 11: Introduction to Recursion</TITLE>
</HEAD>
<BODY>
<HR>
<CITE>Simply Scheme:</CITE>
<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT
<H2>Chapter 11</H2>
<H1>Introduction to Recursion</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../simply.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"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew
Wright</A><BR>University of California, Santa Barbara</CITE>
<TR><TD align="right"><BR>
<TR><TD align="right"><A HREF="../pdf/ssch11.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../ss-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="part4.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch12/leap.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="http://mitpress.mit.edu/0262082810">MIT
Press web page for <CITE>Simply Scheme</CITE></A>
</TABLE></TABLE>
<HR>
<P><A NAME="swallow"></A>
<P><TABLE>
<TR><TD> I know an old lady who swallowed a fly.
<TD> She swallowed the cat to catch the bird.
<TR><TD> I don't know why she swallowed the fly.
<TD> She swallowed the bird to catch the spider
<TR><TD> Perhaps she'll die.
<TD> that wriggled and jiggled and tickled inside her.
<TR><TD>
<TD> She swallowed the spider to catch the fly.
<TR><TD> I know an old lady who swallowed a spider
<TD> I don't know why she swallowed the fly.
<TR><TD> that wriggled and jiggled and tickled inside her.
<TD> Perhaps she'll die.
<TR><TD> She swallowed the spider to catch the fly.
<TD>
<TR><TD> I don't know why she swallowed the fly.
<TD> I know an old lady who swallowed a dog.
<TR><TD> Perhaps she'll die.
<TD> What a hog, to swallow a dog!
<TR><TD>
<TD> She swallowed the dog to catch the cat.
<TR><TD> I know an old lady who swallowed a bird.
<TD> She swallowed the cat to catch the bird.
<TR><TD> How absurd, to swallow a bird!
<TD> She swallowed the bird to catch the spider
<TR><TD> She swallowed the bird to catch the spider
<TD> that wriggled and jiggled and tickled inside her.
<TR><TD> that wriggled and jiggled and tickled inside her.
<TD> She swallowed the spider to catch the fly.
<TR><TD> She swallowed the spider to catch the fly.
<TD> I don't know why she swallowed the fly.
<TR><TD> I don't know why she swallowed the fly.
<TD> Perhaps she'll die.
<TR><TD> Perhaps she'll die.
<TD>
<TR><TD>
<TD> I know an old lady who swallowed a horse.
<TR><TD> I know an old lady who swallowed a cat.
<TD> She's dead of course!
<TR><TD> Imagine that, to swallow a cat.
<TD>
<TR><TD> <TD> <TR><TD> <TD>
<TR><TD> 100 bottles of beer on the wall,
<TD> 98 bottles of beer on the wall,
<TR><TD> 100 bottles of beer.
<TD> 98 bottles of beer.
<TR><TD> If one of those bottles should happen to fall,
<TD> If one of those bottles should happen to fall,
<TR><TD> 99 bottles of beer on the wall.
<TD> 97 bottles of beer on the wall.
<TR><TD>
<TD>
<TR><TD> 99 bottles of beer on the wall,
<TD> 97 bottles of beer on the wall,
<TR><TD> 99 bottles of beer.
<TD> 97 bottles of beer.
<TR><TD> If one of those bottles should happen to fall,
<TD> If one of those bottles should happen to fall,
<TR><TD> 98 bottles of beer on the wall.
<TD> 96 bottles of beer on the wall…
</TABLE>
<P> <P>
<P>In the next few chapters we're going to talk about <EM>recursion:</EM> solving a big problem by reducing it to a similar,
smaller subproblem. Actually that's a little backward from the old lady in
the song, who turned her little problem into a similar but <EM>bigger</EM>
problem! As the song warns us, this can be fatal.
<P>Here's the first problem we'll solve. We want a function that
works like this:
<P><PRE>> (<A NAME="g1"></A>downup 'ringo)
(RINGO RING RIN RI R RI RIN RING RINGO)
> (downup 'marsupial)
(MARSUPIAL
MARSUPIA
MARSUPI
MARSUP
MARSU
MARS
MAR
MA
M
MA
MAR
MARS
MARSU
MARSUP
MARSUPI
MARSUPIA
MARSUPIAL)
</PRE>
<P>None of the tools that we've used so far will handle this problem. It's not
a "compute this function for each letter of the word" problem, for which
we could use <CODE>every</CODE>.<A NAME="text1" HREF="recursion#ft1">[1]</A> Rather, we have to think
about the entire word in a rather complicated way.
<P>We're going to solve this problem using recursion. It turns out that the
idea of recursion is both very powerful—we can solve a <EM>lot</EM> of
problems using it—and rather tricky to understand. That's why we're going
to explain recursion several different ways in the coming chapters. Even
after you understand one of them, you'll probably find that thinking about
recursion from another point of view enriches your ability to use this idea.
The explanation in this chapter is based on the <EM>combining method.</EM>
<P><H2>A Separate Procedure for Each Length</H2>
<P>Since we don't yet know how to solve the <CODE>downup</CODE> problem in general,
let's start with a particular case that we <EM>can</EM> solve. We'll write a
version of <CODE>downup</CODE> that works only for one-letter words:
<P><PRE>(define (downup1 wd)
(se wd))
> (downup1 'a)
(A)
</PRE>
<P>So far so good! This isn't a very versatile program, but it does have the
advantage of being easy to write.
<P>Now let's see if we can do two-letter words:
<P><PRE>(define (downup2 wd)
(se wd (first wd) wd))
> (downup2 'be)
(BE B BE)
</PRE>
<P>Moving right along…
<PRE>(define (downup3 wd)
(se wd
(bl wd)
(first wd)
(bl wd)
wd))
> (downup3 'foo)
(FOO FO F FO FOO)
</PRE>
<P>We could continue along these lines, writing procedures <CODE>downup4</CODE> and so
on. If we knew that the longest word in English had 83 letters, we could
write all of the single-length <CODE>downup</CODE>s up to <CODE>downup83</CODE>, and then
write one overall <CODE>downup</CODE> procedure that would consist of an enormous
<CODE>cond</CODE> with 83 clauses, one for each length.
<P><H2>Use What You Have to Get What You Need</H2>
<P>But that's a terrible idea. We'd get really bored, and start making a lot
of mistakes, if we tried to work up to <CODE>downup83</CODE> this way.
<P>The next trick is to notice that the middle part of what <CODE>(downup3 'foo)</CODE> does is just like <CODE>(downup2 'fo)</CODE>:
<P><CENTER><IMG SRC="../ss-pics/uparrow.jpg" ALT="figure: uparrow"></CENTER>
<P>
<P>So we can find the parts of <CODE>downup3</CODE> that are responsible for
those three words:
<P><CENTER><IMG SRC="../ss-pics/curvedarrow.jpg" ALT="figure: curvedarrow"></CENTER>
<P>
<P>and replace them with an invocation of <CODE>downup2</CODE>:
<P><PRE>(define (downup3 wd)
(se wd (downup2 (bl wd)) wd))
</PRE>
<P>How about <CODE>downup4</CODE>? Once we've had this great idea about using <CODE>downup2</CODE> to help with <CODE>downup3</CODE>, it's not hard to continue the pattern:
<P><PRE>(define (downup4 wd)
(se wd (downup3 (bl wd)) wd))
> (downup4 'paul)
(PAUL PAU PA P PA PAU PAUL)
</PRE>
<P>The reason we can fit the body of <CODE>downup4</CODE> on one line is that most of
its work is done for it by <CODE>downup3</CODE>. If we continued writing each new
<CODE>downup</CODE> procedure independently, as we did in our first attempt at <CODE>downup3</CODE>, our procedures would be getting longer and longer. But this new
way avoids that.
<P><PRE>(define (downup59 wd)
(se wd (downup58 (bl wd)) wd))
</PRE>
<P>Also, although it may be harder to notice, we can even rewrite <CODE>downup2</CODE>
along the same lines:
<P><PRE>(define (downup2 wd)
(se wd (downup1 (bl wd)) wd))
</PRE>
<P><H2>Notice That They're All the Same</H2>
<P>Although <CODE>downup59</CODE> was easy to write, the problem is that it won't work
unless we also define <CODE>downup58</CODE>, which in turn depends on <CODE>downup57</CODE>, and so on. This is a lot of repetitive, duplicated, and
redundant typing. Since these procedures are all basically the same, what
we'd like to do is combine them into a single procedure:
<P><PRE>(define (downup wd) ;; first version
(se wd (downup (bl wd)) wd))
</PRE>
<P>Isn't this a great idea? We've written one short procedure that
serves as a kind of abbreviation for 59 other ones.
<P><H2>Notice That They're Almost All the Same</H2>
<P>Unfortunately, it doesn't work.
<P><PRE>> (downup 'toe)
ERROR: Invalid argument to BUTLAST: ""
</PRE>
<P>What's gone wrong here? Not quite every numbered <CODE>downup</CODE> looks like
<P><PRE>(define (downup<EM>n</EM> wd)
(se wd (downup<EM>n</EM>-<EM>1</EM> (bl wd)) wd))
</PRE>
<P>The only numbered <CODE>downup</CODE> that doesn't follow the pattern is <CODE>downup1</CODE>:
<P><PRE>(define (downup1 wd)
(se wd))
</PRE>
<P>So if we collapse all the numbered <CODE>downup</CODE>s into a single procedure, we
have to treat one-letter words as a special case:
<P><PRE>(define (<A NAME="g2"></A>downup wd)
(if (= (count wd) 1)
(se wd)
(se wd (downup (bl wd)) wd)))
> (downup 'toe)
(TOE TO T TO TOE)
> (downup 'banana)
(BANANA BANAN BANA BAN BA B BA BAN BANA BANAN BANANA)
</PRE>
<P>This version of <CODE>downup</CODE> will work for any length word, from <CODE>a</CODE> to
<CODE>pneumonoultramicroscopicsilicovolcanoconinosis</CODE><A NAME="text2" HREF="recursion#ft2">[2]</A> or beyond.
<P><H2>Base Cases and Recursive Calls</H2>
<P><CODE>Downup</CODE> illustrates the structure of every recursive procedure. There is
a choice among expressions to evaluate: At least one is a <EM>recursive</EM>
<A NAME="g3"></A>
<A NAME="g4"></A>
case, in which the procedure (e.g., <CODE>downup</CODE>) itself is invoked with a
smaller argument; at least one is a <EM>base</EM> case, that is, one that can
be
<A NAME="g5"></A>
<A NAME="g6"></A>
solved without calling the procedure recursively. For <CODE>downup</CODE>, the base
case is a single-letter argument.
<P>How can this possibly work? We're defining <CODE>downup</CODE> in terms of <CODE>downup</CODE>. In English class, if the teacher asks you to define "around,"
you'd better not say, "You know, <EM>around!</EM>" But we appear to be
doing just that. We're telling Scheme: "In order to find <CODE>downup</CODE> of a
word, find <CODE>downup</CODE> of another word."
<P>The secret is that it's not just any old other word. The new word is
<EM>smaller</EM> than the word we were originally asked to <CODE>downup</CODE>. So
we're saying, "In order to find <CODE>downup</CODE> of a word, find <CODE>downup</CODE>
of a shorter word." We are posing a whole slew of <EM>subproblems</EM>
asking for the <CODE>downup</CODE> of words smaller than the one we started with.
So if someone asks us the <CODE>downup</CODE> of <CODE>happy</CODE>, along the way we have
to compute the <CODE>downup</CODE>s of <CODE>happ</CODE>, <CODE>hap</CODE>, <CODE>ha</CODE>, and <CODE>h</CODE>.
<P>A recursive procedure doesn't work unless every possible argument can
eventually be reduced to some base case. When we are asked for <CODE>downup</CODE>
of <CODE>h</CODE>, the procedure just knows what to do without calling itself
recursively.
<P>We've just said that there has to be a base case. It's also important that
each recursive call has to get us somehow closer to the base case. For
<CODE>downup</CODE>, "closer" means that in the recursive call we use a shorter
word. If we were computing a numeric function, the base case might be an
argument of zero, and the recursive calls would use smaller numbers.
<P><H2>Pig Latin</H2>
<P>Let's take another example; we'll write the <A NAME="g7"></A><A NAME="g8"></A>Pig Latin procedure
that we showed off in Chapter 1. We're trying to take a word, move
all the initial consonants to the end, and add "ay."
<P>The simplest case is that there are no initial consonants to move:
<P><PRE>(define (pigl0 wd)
(word wd 'ay))
> (pigl0 'alabaster)
ALABASTERAY
</PRE>
<P>(This will turn out to be the base case of our eventual
recursive procedure.)
<P>The next-simplest case is a word that starts with one consonant. The
obvious way to write this is
<P><PRE>(define (pigl1 wd) ;; obvious version
(word (bf wd) (first wd) 'ay))
> (pigl1 'salami)
ALAMISAY
</PRE>
<P>but, as in the <CODE>downup</CODE> example, we'd like to find a way to use
<CODE>pigl0</CODE> in implementing <CODE>pigl1</CODE>. This case isn't exactly like <CODE>downup</CODE>, because there isn't a piece of the return value that we can draw a
box around to indicate that <CODE>pigl0</CODE> returns that piece. Instead, <CODE>pigl0</CODE> puts the letters <CODE>ay</CODE> at the end of some word, and so does <CODE>pigl1</CODE>. The difference is that <CODE>pigl1</CODE> puts <CODE>ay</CODE> at the end of
a <EM>rearrangement</EM> of its argument word. To make this point clearer,
we'll rewrite <CODE>pigl1</CODE> in a way that separates the rearrangement from the
<CODE>ay</CODE> addition:
<P><PRE>(define (pigl1 wd)
(word (word (bf wd) (first wd))
'ay))
> (pigl1 'pastrami)
ASTRAMIPAY
</PRE>
<P>Now we actually replace the <CODE>pigl0</CODE>-like part with an
invocation. We want to replace <CODE>(word <CODE><EM>something</EM></CODE> 'ay)</CODE> with
<CODE>(pigl0 <CODE><EM>something</EM></CODE>)</CODE>. If we use <CODE>pigl0</CODE> to attach the
<CODE>ay</CODE> at the end, our new version of <CODE>pigl1</CODE> looks like this:
<P><PRE>(define (pigl1 wd)
(pigl0 (word (bf wd) (first wd))))
</PRE>
<P>How about a word starting with two consonants? By now we know that we're
going to try to use <CODE>pigl1</CODE> as a helper procedure, so let's skip writing
<CODE>pigl2</CODE> the long way. We can just move the first consonant to the end
of the word, and handle the result, a word with only one consonant in front,
with <CODE>pigl1</CODE>:
<P><PRE>(define (pigl2 wd)
(pigl1 (word (bf wd) (first wd))))
> (pigl2 'trample)
AMPLETRAY
</PRE>
<P>For a three-initial-consonant word we move one letter to the end and call
<CODE>pigl2</CODE>:
<P><PRE>(define (pigl3 wd)
(pigl2 (word (bf wd) (first wd))))
> (pigl3 'chrome)
OMECHRAY
</PRE>
<P>So how about a version that will work for any word?<A NAME="text3" HREF="recursion#ft3">[3]</A> The recursive case will involve taking the <CODE>pigl</CODE> of <CODE>(word (bf wd) (first wd))</CODE>, to match the pattern we found in
<CODE>pigl1</CODE>, <CODE>pigl2</CODE>, and <CODE>pigl3</CODE>. The base case will be a word
that begins with a vowel, for which we'll just add <CODE>ay</CODE> on the end, as
<CODE>pigl0</CODE> does:
<P><PRE>(define (<A NAME="g9"></A>pigl wd)
(if (member? (first wd) 'aeiou)
(word wd 'ay)
(pigl (word (bf wd) (first wd)))))
</PRE>
<P>It's an unusual sense in which <CODE>pigl</CODE>'s recursive call poses a
"smaller" subproblem. If we're asked for the <CODE>pigl</CODE> of <CODE>scheme</CODE>,
we construct a new word, <CODE>chemes</CODE>, and ask for <CODE>pigl</CODE> of that. This
doesn't seem like much progress. We were asked to translate <CODE>scheme</CODE>, a
six-letter word, into Pig Latin, and in order to do this we need to
translate <CODE>chemes</CODE>, another six-letter word, into Pig Latin.
<P>But actually this <EM>is</EM> progress, because for Pig Latin the base case
isn't a one-letter word, but rather a word that starts with a vowel.
<CODE>Scheme</CODE> has three consonants before the first vowel; <CODE>chemes</CODE> has
only two consonants before the first vowel.
<P><CODE>Chemes</CODE> doesn't begin with a vowel either, so we construct the word
<CODE>hemesc</CODE> and try to <CODE>pigl</CODE> that. In order to find <CODE>(pigl 'hemesc)</CODE> we need to know <CODE>(pigl 'emesch)</CODE>. Since <CODE>emesch</CODE>
<EM>does</EM> begin with a vowel, <CODE>pigl</CODE> returns <CODE>emeschay</CODE>. Once we
know <CODE>(pigl 'emesch)</CODE>, we've thereby found the answer to our original
question.
<P><H2>Problems for You to Try</H2>
<P>You've now seen two examples of recursive procedures that we developed using
the combining method. We started by writing special-case procedures to
handle small problems of a particular size, then simplified the larger
versions by using smaller versions as helper procedures. Finally we
combined all the nearly identical individual versions into a single
recursive procedure, taking care to handle the base case separately.
<P>Here are a couple of problems that can be solved with recursive procedures.
Try them yourself before reading further. Then we'll show you our solutions.
<P><PRE>> (<A NAME="g10"></A>explode 'dynamite)
(D Y N A M I T E)
> (<A NAME="g11"></A>letter-pairs 'george)
(GE EO OR RG GE)
</PRE>
<P><H2>Our Solutions</H2>
<P>What's the smallest word we can <CODE>explode</CODE>? There's no reason we
can't explode an empty word:
<P><PRE>(define (explode0 wd)
'())
</PRE>
<P>That wasn't very interesting, though. It doesn't suggest a
pattern that will apply to larger words. Let's try a few larger cases:
<P><PRE>(define (explode1 wd)
(se wd))
(define (explode2 wd)
(se (first wd) (last wd)))
(define (explode3 wd)
(se (first wd) (first (bf wd)) (last wd)))
</PRE>
<P>With <CODE>explode3</CODE> the procedure is starting to get complicated enough that
we want to find a way to use <CODE>explode2</CODE> to help. What <CODE>explode3</CODE>
does is to pull three separate letters out of its argument word, and collect
the three letters in a sentence. Here's a sample:
<P><PRE>> (explode3 'tnt)
(T N T)
</PRE>
<P><CODE>Explode2</CODE> pulls <EM>two</EM> letters out of a word and
collects them in a sentence. So we could let <CODE>explode2</CODE> deal with two
of the letters of our three-letter argument, and handle the remaining letter
separately:
<P><PRE>(define (explode3 wd)
(se (first wd) (explode2 (bf wd))))
</PRE>
<P>We can use similar reasoning to define <CODE>explode4</CODE> in terms of
<CODE>explode3</CODE>:
<P><PRE>(define (explode4 wd)
(se (first wd) (explode3 (bf wd))))
</PRE>
<P>Now that we see the pattern, what's the base case? Our first three
numbered <CODE>explode</CODE>s are all different in shape from <CODE>explode3</CODE>,
but now that we know what the pattern should be we'll find that we
can write <CODE>explode2</CODE> in terms of <CODE>explode1</CODE>, and even <CODE>explode1</CODE>
in terms of <CODE>explode0</CODE>:
<P><PRE>(define (explode2 wd)
(se (first wd) (explode1 (bf wd))))
(define (explode1 wd)
(se (first wd) (explode0 (bf wd))))
</PRE>
<P>We would never have thought to write <CODE>explode1</CODE> in that
roundabout way, especially since <CODE>explode0</CODE> pays no attention to
its argument, so computing the <CODE>butfirst</CODE> doesn't contribute
anything to the result, but by following the pattern we can let the
recursive case handle one-letter and two-letter words, so that only
zero-letter words have to be special:
<P><A NAME="explodepage"></A>
<PRE>(define (explode wd)
(if (empty? wd)
'()
(se (first wd) (explode (bf wd)))))
</PRE>
<P>Now for <CODE>letter-pairs</CODE>. What's the smallest word we can use as its
argument? Empty and one-letter words have no letter pairs in them:
<P><PRE>(define (letter-pairs0 wd)
'())
(define (letter-pairs1 wd)
'())
</PRE>
<P>This pattern is not very helpful.
<P><PRE>(define (letter-pairs2 wd)
(se wd))
(define (letter-pairs3 wd)
(se (bl wd) (bf wd)))
(define (letter-pairs4 wd)
(se (bl (bl wd))
(bl (bf wd))
(bf (bf wd))))
</PRE>
<P>Again, we want to simplify <CODE>letter-pairs4</CODE> by using <CODE>letter-pairs3</CODE>
to help. The problem is similar to <CODE>explode</CODE>: The value returned by
<CODE>letter-pairs4</CODE> is a three-word sentence, and we can use <CODE>letter-pairs3</CODE> to generate two of those words.
<P><PRE>> (letter-pairs4 'nems)
(NE <CODE STYLE="border:solid">EM MS</CODE>)
</PRE>
<P>This gives rise to the following procedure:
<P><PRE>(define (letter-pairs4 wd)
(se (bl (bl wd))
(letter-pairs3 (bf wd))))
</PRE>
<P>Does this pattern work for defining <CODE>letter-pairs5</CODE> in terms of <CODE>letter-pairs4</CODE>?
<P><PRE>(define (letter-pairs5 wd) ;; wrong
(se (bl (bl wd))
(letter-pairs4 (bf wd))))
> (letter-pairs5 'bagel)
(BAG AG GE EL)
</PRE>
<P>The problem is that <CODE>(bl (bl wd))</CODE> means "the first two letters of <CODE>wd</CODE>" only when <CODE>wd</CODE> has four letters. In order to be able to
generalize the pattern, we need a way to ask for the first two letters of a
word that works no matter how long the word is. You wrote a procedure to
solve this problem in Exercise :
<P><PRE>(define (first-two wd)
(word (first wd) (first (bf wd))))
</PRE>
<P>Now we can use this for <CODE>letter-pairs4</CODE> and <CODE>letter-pairs5</CODE>:
<P><PRE>(define (letter-pairs4 wd)
(se (first-two wd) (letter-pairs3 (bf wd))))
(define (letter-pairs5 wd)
(se (first-two wd) (letter-pairs4 (bf wd))))
</PRE>
<P><EM>This</EM> pattern <EM>does</EM> generalize.
<P><PRE>(define (letter-pairs wd)
(if (<= (count wd) 1)
'()
(se (first-two wd)
(letter-pairs (bf wd)))))
</PRE>
<P>Note that we treat two-letter and three-letter words as recursive
cases and not as base cases. Just as in the example of <CODE>explode</CODE>, we
noticed that we could rewrite <CODE>letter-pairs2</CODE> and <CODE>letter-pairs3</CODE> to
follow the same pattern as the larger cases:
<P><PRE>(define (letter-pairs2 wd)
(se (first-two wd)
(letter-pairs1 (bf wd))))
(define (letter-pairs3 wd)
(se (first-two wd)
(letter-pairs2 (bf wd))))
</PRE>
<P><H2>Pitfalls</H2>
<P>Every recursive procedure must include two parts: one or more recursive
cases, in which the recursion reduces the size of the problem, and one or
more base cases, in which the result is computable without recursion. For
example, our first attempt at <CODE>downup</CODE> fell into this pitfall because we
had no base case.
<P>Don't be too eager to write the recursive procedure. As we showed
in the <CODE>letter-pairs</CODE> example, what looks like a generalizable
pattern may not be.
<P><H2>Boring Exercises</H2>
<P><B>11.1</B> Write <CODE>downup4</CODE> using only the word and sentence primitive procedures.
<P>
<B>11.2</B> [<A HREF="../ssch8/higher.html#countums">8.12</A>]<A NAME="text4" HREF="recursion#ft4">[4]</A>
When you teach a class, people will get distracted if you say "um" too many
times. Write a <CODE><A NAME="g12"></A>count-ums</CODE> that counts the number of times "um"
appears in a sentence:
<A NAME="countumsrec"></A>
<P><PRE>> (count-ums
'(today um we are going to um talk about the combining um method))
3
</PRE>
<P>Here are some special-case <CODE>count-ums</CODE>
procedures for sentences of particular lengths:
<P><PRE>(define (count-ums0 sent)
0)
(define (count-ums1 sent)
(if (equal? 'um (first sent))
1
0))
(define (count-ums2 sent)
(if (equal? 'um (first sent))
(+ 1 (count-ums1 (bf sent)))
(count-ums1 (bf sent))))
(define (count-ums3 sent)
(if (equal? 'um (first sent))
(+ 1 (count-ums2 (bf sent)))
(count-ums2 (bf sent))))
</PRE>
<P>Write <CODE>count-ums</CODE> recursively.
<P>
<B>11.3</B> [<A HREF="../ssch8/higher.html#unspell">8.13</A>]
Write a procedure <CODE><A NAME="g13"></A>phone-unspell</CODE> that takes a spelled version of
a phone number, such as <CODE>POPCORN</CODE>, and returns the real phone number, in
this case <CODE>7672676</CODE>. You will need a helper procedure that
translates a single letter into a digit:
<A NAME="unspellrec"></A>
<P><PRE>(define (unspell-letter letter)
(cond ((member? letter 'abc) 2)
((member? letter 'def) 3)
((member? letter 'ghi) 4)
((member? letter 'jkl) 5)
((member? letter 'mno) 6)
((member? letter 'prs) 7)
((member? letter 'tuv) 8)
((member? letter 'wxy) 9)
(else 0)))
</PRE>
<P>Here are some some special-case <CODE>phone-unspell</CODE> procedures:
<P><PRE>(define (phone-unspell1 wd)
(unspell-letter wd))
(define (phone-unspell2 wd)
(word (unspell-letter (first wd))
(unspell-letter (first (bf wd)))))
(define (phone-unspell3 wd)
(word (unspell-letter (first wd))
(unspell-letter (first (bf wd)))
(unspell-letter (first (bf (bf wd))))))
</PRE>
<P>Write <CODE>phone-unspell</CODE> recursively.
<P>
<H2>Real Exercises</H2>
<P><STRONG>Use recursion to solve these problems, not higher order
functions (Chapter 8)!</STRONG>
<P><B>11.4</B> Who first said "use what you have to get what you need"?
<P>
<B>11.5</B> Write a procedure <CODE><A NAME="g14"></A>initials</CODE> that takes a sentence as its
argument and returns a sentence of the first letters in each of the
sentence's words:
<P><PRE>> (initials '(if i needed someone))
(I I N S)
</PRE>
<P>
<B>11.6</B> Write a procedure <CODE><A NAME="g15"></A>countdown</CODE> that works like this:
<P><PRE>> (countdown 10)
(10 9 8 7 6 5 4 3 2 1 BLASTOFF!)
> (countdown 3)
(3 2 1 BLASTOFF!)
</PRE>
<P>
<B>11.7</B> Write a procedure <CODE><A NAME="g16"></A>copies</CODE> that takes a number and a word as
arguments and returns a sentence containing that many copies of the given
word:
<A NAME="copies"></A>
<P><PRE>> (copies 8 'spam)
(SPAM SPAM SPAM SPAM SPAM SPAM SPAM SPAM)
</PRE>
<P>
<HR>
<A NAME="ft1" HREF="recursion#text1">[1]</A> If your instructor has asked you to read
Part IV before Part III, ignore that sentence.<P>
<A NAME="ft2" HREF="recursion#text2">[2]</A> It's a
disease. Coal miners get it.<P>
<A NAME="ft3" HREF="recursion#text3">[3]</A> As it happens,
there are no English words that start with more than four consonants.
(There are only a few even with four; "phthalate" is one, and some others
are people's names, such as "Schneider.") So we could solve the problem
without recursion by writing the specific procedures up to <CODE>pigl4</CODE> and
then writing a five-way <CODE>cond</CODE> to choose the appropriate specific case.
But as you will see, it's easier to solve the more general case! A single
recursive procedure, which can handle even nonexistent words with hundreds of
initial consonants, is less effort than the conceptually simpler
four-consonant version.<P>
<A NAME="ft4" HREF="recursion#text4">[4]</A> Exercise <A HREF="../ssch8/higher.html#countums">8.12</A> in Part III asks you to solve this
same problem using higher-order functions. Here we are asking you to use
recursion. Whenever we pose the same problem in both parts, we'll
cross-reference them in brackets as we did here. When you see the problem
for the second time, you might want to consult your first solution for ideas.<P>
<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P>
<A HREF="part4.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch12/leap.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|