<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.html#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.html#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.html#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.html#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.html#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.html#text2">[2]</A> It's a
disease. Coal miners get it.<P>
<A NAME="ft3" HREF="recursion.html#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.html#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>