<P>
<P> <A NAME="hands"></A>
<CENTER><IMG SRC="../ss-pics/hands.jpg" ALT="figure: hands"></CENTER><P><CENTER><EM>Drawing Hands,</EM> by M. C. Escher (lithograph,
1948)
</CENTER><P>
<HTML>
<HEAD>
<TITLE>Simply Scheme: Introducing Computer Science ch 12: The Leap of Faith</TITLE>
</HEAD>
<BODY>
<HR>
<CITE>Simply Scheme:</CITE>
<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT
<H2>Chapter 12</H2>
<H1>The Leap of Faith</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/ssch12.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="../ssch11/recursion.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch13/convince-recur.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>In the combining method, we build up to a recursive procedure by writing a
number of special-case nonrecursive procedures, starting with small arguments
and working toward larger ones. We find a generalizable way to use a
smaller version in writing a larger one. As a result, all our procedures
end up looking nearly the same, so we combine them into one procedure.
<P>The combining method is a good way to begin thinking about recursion because
each step of a solution is clearly justified by earlier steps. The sequence
of events by which we get from a problem statement to a Scheme procedure is
clear and straightforward. The disadvantage of the combining method,
though, is that it involves a lot of drudgery, not all of which really helps
toward the ultimate solution. In this chapter we're going to develop a new
method called <EM>the leap of faith</EM> that overcomes this difficulty.
<P><H2>From the Combining Method to the Leap of Faith</H2>
<P>Let's look again at the way we developed the <CODE>letter-pairs</CODE> procedure in
the last chapter. We went through several steps:
<P><P><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">We wrote specific versions for zero-, one-, two-, and three-letter words.
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">We wrote <CODE>letter-pairs4</CODE>, decided it was too complicated, and looked
for a way to use <CODE>letter-pairs3</CODE> to help.
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Having rewritten <CODE>letter-pairs4</CODE>, we tried to write <CODE>letter-pairs5</CODE> using the same pattern. Since it didn't quite work, we
revised the pattern.
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">We generalized the pattern to write an unnumbered, recursive <CODE>letter-pairs</CODE>.
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">We checked to make sure that the recursive pattern would work for
two-letter and three-letter words.
</TABLE><TABLE><TR><TH align="right" valign="top">•<TD> <TD valign="top">Since the pattern doesn't work for zero- or one-letter words, we made
those the base cases.
</TABLE>
<P>
Although we needed the lowest numbered procedures in order to make
the entire collection of numbered procedures work, those low-numbered ones
didn't contribute to the critical step of finding a generalizable pattern.
Once you understand the idea of recursion, writing the individual procedures
is wasted effort.
<P>In the leap of faith method, we short-circuit this process in two ways.
First, we don't bother thinking about small examples; we begin with, for
example, a seven-letter word. Second, we don't use our example to write a
particular numbered procedure; we write the recursive version directly.
<P><H2>Example: <CODE><B>Reverse</B></CODE></H2>
<P>We're going to write, using the leap of faith method, a recursive procedure
to reverse the letters of a word:
<P><PRE>> (reverse 'beatles)
SELTAEB
</PRE>
<P>Is there a <CODE>reverse</CODE> of a smaller argument lurking within
that return value? Yes, many of them. For example, <CODE>LTA</CODE> is the
<CODE>reverse</CODE> of the word <CODE>ATL</CODE>. But it will be most helpful if we
find a smaller subproblem that's only <EM>slightly</EM> smaller. (This idea
corresponds to writing <CODE>letter-pairs7</CODE> using <CODE>letter-pairs6</CODE> in the
combining method.) The closest smaller subproblem to our original problem
is to find the <CODE>reverse</CODE> of a word one letter shorter than <CODE>beatles</CODE>.
<P><PRE>> (reverse 'beatle)
ELTAEB
</PRE>
<P>This result is pretty close to the answer we want for <CODE>reverse</CODE> of <CODE>beatles</CODE>. What's the relationship between <CODE>ELTAEB</CODE>,
the answer to the smaller problem, and <CODE>SELTAEB</CODE>, the answer to the
entire problem? There's one extra letter, <CODE>S</CODE>, at the beginning. Where
did the extra letter come from? Obviously, it's the last letter of <CODE>beatles</CODE>.<A NAME="text1" HREF="leap#ft1">[1]</A>
<P>This may seem like a sequence of trivial observations leading nowhere. But
as a result of this investigation, we can translate what we've learned
directly into Scheme. In English: "the <CODE>reverse</CODE> of a word consists
of its last letter followed by the <CODE>reverse</CODE> of its <CODE>butlast</CODE>." In
Scheme:
<P><PRE>(define (reverse wd) ;; unfinished
(word (last wd)
(reverse (bl wd))))
</PRE>
<P><H2>The Leap of Faith</H2>
<P>If we think of this Scheme fragment merely as a statement of a true fact
about <CODE>reverse</CODE>, it's not very remarkable. The amazing part is that
this fragment is <EM>runnable!</EM><A NAME="text2" HREF="leap#ft2">[2]</A> 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>reverse</CODE>
when you haven't written it yet?"
<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>reverse</CODE> procedure that can compute <CODE>(reverse 'paul)</CODE>, we
assume that <CODE>(reverse 'aul)</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 four-letter <CODE>reverse</CODE> is relying on the three-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>reverse1</CODE> through <CODE>reverse3</CODE> "by hand."
<P>The reason that our 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>whatever3</CODE>
before we even raised the question of <CODE>whatever4</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 we can write
the recursive solution immediately, without bothering with many individual
cases. The reason we 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 Base Case</H2>
<P>Of course, our definition of <CODE>reverse</CODE> isn't finished yet: As always, we
need a base case. But base cases are the easy part. Base cases transform
simple arguments into simple answers, and you can do that transformation in
your head.
<P>For example, what's the simplest argument to <CODE>reverse</CODE>? If you
answered "a one-letter word" then pick a one-letter word and decide what
the result should be:
<P><PRE>> (reverse 'x)
X
</PRE>
<P><CODE>reverse</CODE> of a one-letter word should just be that same word:
<P><PRE>(define (reverse wd)
(if (= (count wd) 1)
wd
(word (last wd)
(reverse (bl wd)))))
</PRE>
<P><H2>Example: <CODE><B>Factorial</B></CODE></H2>
<P>We'll use the leap of faith method to solve another problem that
we haven't already solved with the combining method.
<P>The factorial of a number <EM>n</EM> is defined as 1×2×···×<EM>n</EM>. So the factorial of 5 (written "5!") is 1×2×3×4×5. Suppose you want Scheme to figure out the factorial of
some large number, such as 843. You start from the definition: 843! is 1×2×···×842×843. Now you have to look for
another factorial problem whose answer will help us find the answer to
843!. You might notice that 2!, that is, 1×2, is part of 843!,
but that doesn't help very much because there's no simple relationship
between 2! and 843!. A more fruitful observation would be that 842!
is 1×···×842—that is, all but the last number in the
product we're trying to compute. So 843! = 843×842!. In general,
<EM>n</EM>! is <EM>n</EM>×(<EM>n</EM>-1)!. We can embody this idea in a Scheme procedure:
<P><PRE>(define (factorial n) ;; first version
(* n (factorial (- n 1))))
</PRE>
<P>Asking for (<EM>n</EM>-1)! is the leap of faith. We're expressing an
answer we don't know, 843!, in terms of another answer we don't know,
842!. But since 842! is a smaller, similar subproblem, we are confident
that the same algorithm will find it.<A NAME="text3" HREF="leap#ft3">[3]</A>
<P>Remember that in the <CODE>reverse</CODE> problem we mentioned that we could have
chosen either the <CODE>butfirst</CODE> or the <CODE>butlast</CODE> of the argument as the
smaller subproblem? In the case of the <CODE>factorial</CODE> problem we don't
have a similar choice. If we tried to subdivide the problem as
<P><P ALIGN="center">6! = 1×(2×3×4×5×6)</P>
<P>
then the part in
parentheses would <EM>not</EM> be the factorial of a smaller
number.<A NAME="text4" HREF="leap#ft4">[4]</A>
<P>As the base case for <CODE>factorial</CODE>, we'll use 1! = 1.
<P><PRE>(define (<A NAME="g1"></A>factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
</PRE>
<P><H2>Likely Guesses for Smaller Subproblems</H2>
<P>To make the leap of faith method work, we have to find a smaller, similar
subproblem whose solution will help solve the given problem. How do we find
such a smaller subproblem?
<P>In the examples so far, we've generally found it by finding a smaller,
similar <EM>return value</EM> within the return value we're trying to
achieve. Then we worked backward from the smaller solution to figure out
what smaller argument would give us that value. For example, here's how we
solved the <CODE>reverse</CODE> problem:
<P><TABLE><TR><TD>original argument<TD> <CODE>beatles</CODE>
<TR><TD>desired return value<TD> <CODE>SELTAEB</CODE>
<TR><TD>smaller return value<TD> <CODE>ELTAEB</CODE>
<TR><TD>corresponding argument<TD> <CODE>beatle</CODE>
<TR><TD>relationship of arguments
<TD> <CODE>beatle </CODE>is<CODE> (bl 'beatles)</CODE>
<TR><TD>Scheme expression<TD> <CODE>(word (last arg)
<TR><TD> <TD> <CODE> (reverse (bl arg)))
</TABLE>
<P>Similarly, we looked at the definition of 843! and noticed within it
the factorial of a smaller number, 842.
<P>But a smaller return value won't necessarily leap out at us in every case.
If not, there are some likely guesses we can try. For example, if the
problem is about integers, it makes sense to try <EM>n</EM>−1 as a smaller
argument. If the problem is about words or sentences, try the <CODE>butfirst</CODE> or the <CODE>butlast</CODE>. (Often, as in the <CODE>reverse</CODE> example,
either will be helpful.) Once you've guessed at a smaller argument, see
what the corresponding return value should be, then compare that with the
original desired return value as we've described earlier.
<P>In fact, these two argument-guessing techniques would have suggested the same
subproblems that we ended up using in our two examples so far. The reason we
didn't teach these techniques from the beginning is that we don't want you
to think they're essential parts of the leap of faith method. These are
just good guesses; they don't always work. When they don't, you have to be
prepared to think more flexibly.
<P><H2>Example: <CODE><B>Downup</B></CODE></H2>
<P>Here's how we might rewrite <CODE><A NAME="g2"></A>downup</CODE> using the leap of faith
method. Start by looking at the desired return value for a medium-sized
example:
<P><PRE>> (downup 'paul)
(PAUL PAU PA P PA PAU PAUL)
</PRE>
<P>Since this is a procedure whose argument is a word, we guess that
the <CODE>butfirst</CODE> or the <CODE>butlast</CODE> might be helpful.
<P><PRE>> (downup 'aul)
(AUL AU A AU AUL)
> (downup 'pau)
(PAU PA P PA PAU)
</PRE>
<P>This is a case in which it matters which we choose; the solution for the
<CODE>butfirst</CODE> of the original argument doesn't help, but the solution for
the <CODE>butlast</CODE> is most of the solution for the original word. All we
have to do is add the original word itself at the beginning and end:
<P><PRE>(define (downup wd) ;; no base case
(se wd (downup (bl wd)) wd))
</PRE>
<P>As before, this is missing the base case, but by now you know how
to fill that in.
<P><H2>Example: <CODE><B>Evens</B></CODE></H2>
<P>Here's a case in which mindlessly guessing <CODE>butfirst</CODE> or <CODE>butlast</CODE>
doesn't lead to a very good solution. We want a procedure that takes a
sentence as its argument and returns a sentence of the even-numbered words
of the original sentence:
<P><PRE>> (<A NAME="g3"></A>evens '(i want to hold your hand))
(WANT HOLD HAND)
</PRE>
<P>We look at <CODE>evens</CODE> of the <CODE>butfirst</CODE> and <CODE>butlast</CODE> of
this sentence:
<P><PRE>> (evens '(want to hold your hand))
(TO YOUR)
> (evens '(i want to hold your))
(WANT HOLD)
</PRE>
<P><CODE>Butfirst</CODE> is clearly not helpful; it gives all the wrong
words. <CODE>Butlast</CODE> looks promising. The relationship between <CODE>evens</CODE>
of the bigger sentence and <CODE>evens</CODE> of the smaller sentence is that the
last word of the larger sentence is missing from <CODE>evens</CODE> of the smaller
sentence.
<P><PRE>(define (losing-evens sent) ;; no base case
(se (losing-evens (bl sent))
(last sent)))
</PRE>
<P>For a base case, we'll take the empty sentence:
<P><PRE>(define (losing-evens sent)
(if (empty? sent)
'()
(se (losing-evens (bl sent))
(last sent))))
> (losing-evens '(i want to hold your hand))
(I WANT TO HOLD YOUR HAND)
</PRE>
<P>This isn't quite right.
<P>It's true that <CODE>evens</CODE> of <CODE>(i want to hold your hand)</CODE> is the same
as <CODE>evens</CODE> of <CODE>(i want to hold your)</CODE> plus the word <CODE>hand</CODE> at
the end. But what about <CODE>evens</CODE> of <CODE>(i want to hold your)</CODE>? By the
reasoning we've been using, we would expect that to be <CODE>evens</CODE> of <CODE>(i want to hold)</CODE> plus the word <CODE>your</CODE>. But since the word <CODE>your</CODE>
is the fifth word of the argument sentence, it shouldn't be part of the
result at all. Here's how <CODE>evens</CODE> should work:
<P><PRE>> (evens '(i want to hold your))
(WANT HOLD)
> (evens '(i want to hold))
(WANT HOLD)
</PRE>
<P>When the sentence has an odd number of words, its <CODE>evens</CODE> is
the same as the <CODE>evens</CODE> of its <CODE>butlast</CODE>.<A NAME="text5" HREF="leap#ft5">[5]</A> So here's our
new procedure:
<P><PRE>(define (evens sent) ;; better version
(cond ((empty? sent) '())
((odd? (count sent))
(evens (bl sent)))
(else (se (evens (bl sent))
(last sent)))))
</PRE>
<P>This version works, but it's more complicated than necessary. What makes it
complicated is that on each recursive call we switch between two kinds of
problems: even-length and odd-length sentences. If we dealt with the words
two at a time, each recursive call would see the same kind of problem.
<P>Once we've decided to go through the sentence two words at a time, we can
reopen the question of whether to go right-to-left or left-to-right. It
will turn out that the latter gives us the simplest procedure:
<P><PRE>(define (evens sent) ;; best version
(if (<= (count sent) 1)
'()
(se (first (bf sent))
(evens (bf (bf sent))))))
</PRE>
<P>Since we go through the sentence two words at a time, an
odd-length argument sentence always gives rise to an odd-length recursive
subproblem. Therefore, it's not good enough to check for an empty sentence
as the only base case. We need to treat both the empty sentence and one-word
sentences as base cases.
<P><H2>Simplifying Base Cases</H2>
<A NAME="basecasereduce"></A>
<A NAME="g4"></A>
<A NAME="g5"></A>
<P>The leap of faith is mostly about recursive cases, not base cases. In the
examples in this chapter, we've picked base cases without talking about them
much. How do you pick a base case?
<P>In general, we recommend using the smallest possible base case argument,
because that usually leads to the simplest procedures. For example,
consider using the empty word, empty sentence, or zero instead of one-letter
words, one-word sentences, or one.
<P>How can you go about finding the simplest possible base case? Our first
example in this chapter was <CODE>reverse</CODE>. We arbitrarily chose to use
one-letter words as the base case:
<P><PRE>(define (reverse wd)
(if (= (count wd) 1)
wd
(word (last wd)
(reverse (bl wd)))))
</PRE>
<P>Suppose we want to consider whether a smaller base case would work. One
approach is to pick an argument that would be handled by the current base
case, and see what would happen if we tried to let the recursive step handle
it instead. (To go along with this experiment, we pick a smaller base case,
since the original base case should now be handled by the recursive step.)
In this example, we pick a one-letter word, let's say <CODE>m</CODE>, and use that
as the value of <CODE>wd</CODE> in the expression
<P><PRE>(word (last wd)
(reverse (bl wd)))
</PRE>
<P>The result is
<P><PRE>(word (last 'm)
(reverse (bl 'm)))
</PRE>
<P>which is the same as
<P><PRE>(word 'm
(reverse ""))
</PRE>
<P>We want this to have as its value the word <CODE>M</CODE>. This will
work out provided that <CODE>(reverse "")</CODE> has the empty word as its value.
So we could rewrite the procedure this way:
<P><PRE>(define (reverse wd)
(if (empty? wd)
""
(word (last word)
(reverse (bl word)))))
</PRE>
<P>We were led to this empty-word base case by working downward from the needs
of the one-letter case. However, it's also important to ensure that the
return value used for the empty word is the correct value, not only to make
the recursion work, but for an empty word in its own right. That is, we
have to convince ourselves that <CODE>(reverse "")</CODE> should return an empty
word. But it should; the <CODE>reverse</CODE> of any word is a word containing the
same letters as the original word. If the original has no letters, the <CODE>reverse</CODE> must have no letters also. This exemplifies a general principle:
Although we choose a base case argument for the sake of the recursive step,
we must choose the corresponding return value for the sake of the argument
itself, not just for the sake of the recursion.
<P>We'll try the base case reduction technique on <CODE>downup</CODE>:
<P><PRE>(define (downup wd)
(if (= (count wd) 1)
(se wd)
(se wd (downup (bl wd)) wd)))
</PRE>
<P>If we want to use the empty word as the base case, instead of
one-letter words, then we have to ensure that the recursive case can return
a correct answer for a one-letter word. The behavior we want is
<P><PRE>> (downup 'a)
(A)
</PRE>
<P>But if we substitute <CODE>'a</CODE> for <CODE>wd</CODE> in the recursive-case
expression we get
<P><PRE>(se 'a (downup "") 'a)
</PRE>
<P>which will have two copies of the word <CODE>A</CODE> in its value no
matter what value we give to <CODE>downup</CODE> of the empty word. We can't
avoid treating one-letter words as a base case.
<P>In writing <CODE>factorial</CODE>, we used <CODE>1</CODE> as the base case.
<P><PRE>(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
</PRE>
<P>Our principle of base case reduction suggests that we try for <CODE>0</CODE>. To do this, we substitute <CODE>1</CODE> for <CODE>n</CODE> in the recursive case
expression:
<P><PRE>(* 1 (factorial 0))
</PRE>
<P>We'd like this to have the value <CODE>1</CODE>; this will be true only
if we define 0! = 1. Now we can say
<P><PRE>(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
</PRE>
<P>In this case, the new procedure is no simpler than the previous
version. Its only advantage is that it handles a case, 0!, that
mathematicians find useful.
<P>Here's another example in which we can't reduce the base case to an empty
word. In Chapter 11 we used the combining method to write <CODE>letter-pairs</CODE>:
<P><PRE>(define (letter-pairs wd)
(if (<= (count wd) 1)
'()
(se (first-two wd)
(letter-pairs (bf wd)))))
(define (first-two wd)
(word (first wd) (first (bf wd))))
</PRE>
<P>It might occur to you that one-letter words could be handled
by the recursive case, and the base case could then handle only the empty
word. But if you try to evaluate the expression for the recursive case
as applied to a one-letter word, you find that
<P><PRE>(first-two 'a)
</PRE>
<P>is equivalent to
<P><PRE>(word (first 'a) (first (bf 'a)))
</PRE>
<P>which is an error. There is no second letter of a one-letter
word. As soon as you see the expression <CODE>(first (bf wd))</CODE> within
this program, you know that one-letter words must be part of the base case.
The same kind of reasoning can be used in many problems; the base case must
handle anything that's too small to fit the needs of the recursive case.
<P>
<H2>Pitfalls</H2>
<P>One possible pitfall is a recursive case that doesn't make progress,
that is, one that doesn't reduce the size of the problem in the recursive call.
For example, let's say we're trying to write the procedure <CODE>down</CODE> that
works this way:
<P><PRE>> (down 'town)
(TOWN TOW TO T)
</PRE>
<P>Here's an incorrect attempt:
<P><PRE>(define (down wd) ;; wrong!
(if (empty? wd)
'()
(se wd (down (first wd)))))
</PRE>
<P>The recursive call looks as if it reduces the size of the problem,
but try it with an actual example. What's <CODE>first</CODE> of the word <CODE>splat</CODE>? What's <CODE>first</CODE> of that result? What's <CODE>first</CODE> of <EM>that</EM> result?
<P>A pitfall that sounds unlikely in the abstract but is actually
surprisingly common is to try to do the second step of the procedure "by
hand" instead of trusting the recursion to do it. For example, here's
another attempt at that <CODE>down</CODE> procedure:
<P><PRE>(define (down wd) ;; incomplete
(se wd …))
</PRE>
<P>You know the first word in the result has to be the argument
word. Then what? The next thing is the same word with its last letter
missing:
<P><PRE>(define (down wd) ;; wrong!
(se wd (bl wd) …))
</PRE>
<P>Instead of taking care of the entire rest of the problem with a
recursive call, it's tempting to take only one more step, figuring out how
to include the second word of the required solution. But that approach
won't get you to a general recursive solution. Just take the first step
and then trust the recursion for the rest:
<P><PRE>(define (<A NAME="g6"></A>down wd)
(if (empty? wd)
'()
(se wd (down (bl wd)))))
</PRE>
<P>The value returned in the base case of your procedure must be in the
range of the function you are representing. If your function is supposed to
return a number, it must return a number all the time, even in the base
case. You can use this idea to help you check the correctness of the
base case expression.
<P>For example, in <CODE>downup</CODE>, the base case returns <CODE>(se wd)</CODE> for the
base case argument of a one-letter word. How did we think to enclose the
word in a sentence? We know that in the recursive cases <CODE>downup</CODE> always
returns a sentence, so that suggests to us that it must return a sentence in
the base case also.
<P>If your base case doesn't make sense in its own right, it probably
means that you're trying to compensate for a mistake in the recursive case.
<P>For example, suppose you've fallen into the pitfall of trying to handle the
second word of a sentence by hand, and you've written the following
procedure:
<P><PRE>(define (square-sent sent) ;; wrong
(if (empty? sent)
'()
(se (square (first sent))
(square (first (bf sent)))
(square-sent (bf sent)))))
> (square-sent '(2 3))
ERROR: Invalid argument to FIRST: ()
</PRE>
<P>After some experimentation, you find that you can get this example
to work by changing the base case:
<P><PRE>(define (square-sent sent) ;; still wrong
(if (= (count sent) 1)
'()
(se (square (first sent))
(square (first (bf sent)))
(square-sent (bf sent)))))
> (square-sent '(2 3))
(4 9)
</PRE>
<P>The trouble is that the base case doesn't make sense on its own:
<P><PRE>> (square-sent '(7))
()
</PRE>
<P>In fact, this procedure doesn't work for any sentences of length
other than two. The moral is that it doesn't work to correct an error in the
recursive case by introducing an absurd base case.
<P><H2>Boring Exercises</H2>
<P><B>12.1</B> Here is a definition of a procedure that returns the sum of the numbers in
its argument sentence:
<P><PRE>(define (addup nums)
(if (empty? (bf nums))
(first nums)
(+ (first nums) (addup (bf nums)))))
</PRE>
<P>Although this works, it could be simplified by changing the base
case. Do that.
<P>
<B>12.2</B> Fix the bug in the following definition:
<P><PRE>(define (acronym sent) ;; wrong
(if (= (count sent) 1)
(first sent)
(word (first (first sent))
(acronym (bf sent)))))
</PRE>
<P>
<B>12.3</B> Can we reduce the <CODE>factorial</CODE> base case argument from <CODE>0</CODE> to <CODE>-1</CODE>?
If so, show the resulting procedure. If not, why not?
<P>
<P>
<B>12.4</B> Here's the definition of a function <EM>f</EM>:
<P><P><CENTER><IMG SRC="math1.gif" ALT="math display"></CENTER><P>
<P>Implement <EM>f</EM> as a Scheme procedure. What does <EM>f</EM> do?
<P>
<H2>Real Exercises</H2>
<P><EM>Solve all of the following problems with recursive procedures. If
you've read Part III, do not use any higher-order functions such as <CODE>every</CODE>, <CODE>keep</CODE>, or <CODE>accumulate</CODE>.</EM>
<P><B>12.5</B> [<A HREF="../ssch8/higher.html#exagg">8.8</A>]
Write an <CODE><A NAME="g7"></A>exaggerate</CODE> procedure which exaggerates sentences:
<A NAME="exaggrec"></A>
<P><PRE>> (exaggerate '(i ate 3 potstickers))
(I ATE 6 POTSTICKERS)
> (exaggerate '(the chow fun is good here))
(THE CHOW FUN IS GREAT HERE)
</PRE>
<P>It should double all the numbers in the sentence, and it should replace
"good" with "great," "bad" with "terrible," and anything else you
can think of.
<P>
<B>12.6</B> [<A HREF="../ssch8/higher.html#gpa">8.11</A>]
Write a GPA procedure. It should take a sentence of grades as its argument
and return the corresponding grade point average:
<A NAME="gparec"></A>
<P><PRE>> (<A NAME="g8"></A>gpa '(A A+ B+ B))
3.67
</PRE>
<P>Hint: write a helper procedure <CODE><A NAME="g9"></A>base-grade</CODE> that takes
a grade as argument and returns 0, 1, 2, 3, or 4, and another helper
procedure <CODE>grade-modifier</CODE> that returns −.33, 0, or .33, depending on
whether the grade has a minus, a plus, or neither.
<P>
<B>12.7</B> Write a procedure <A NAME="g10"></A><CODE>spell-number</CODE> that spells out the digits of
a number:
<P><PRE>> (spell-number 1971)
(ONE NINE SEVEN ONE)
</PRE>
<P>Use this helper procedure:
<P><PRE>(define (spell-digit digit)
(item (+ 1 digit)
'(zero one two three four five six seven eight nine)))
</PRE>
<P>
<B>12.8</B> Write a procedure <CODE><A NAME="g11"></A>numbers</CODE> that takes a sentence as its argument
and returns another sentence containing only the numbers in the argument:
<P><PRE>> (numbers '(76 trombones and 110 cornets))
(76 110)
</PRE>
<P>
<B>12.9</B> Write a procedure <CODE><A NAME="g12"></A>real-words</CODE> that takes a sentence as argument
and returns all the "real" words of the sentence, using the same rule as
the <CODE>real-word?</CODE> procedure from Chapter 1.
<P>
<B>12.10</B> Write a procedure <CODE><A NAME="g13"></A>remove</CODE> that takes a word and a sentence as
arguments and returns the same sentence, but with all copies of the given
word removed:
<P><PRE>> (remove 'the '(the song love of the loved by the beatles))
(SONG LOVE OF LOVED BY BEATLES)
</PRE>
<P>
<B>12.11</B> Write the procedure <CODE>count</CODE>, which returns the number of words in a
sentence or the number of letters in a word.
<P>
<B>12.12</B> Write a procedure <CODE><A NAME="g14"></A>arabic</CODE> which converts Roman numerals into
Arabic numerals:
<P><PRE>> (arabic 'MCMLXXI)
1971
> (arabic 'MLXVI)
1066
</PRE>
<P>You will probably find the <CODE>roman-value</CODE> procedure from Chapter
6 helpful. Don't forget that a letter can <EM>reduce</EM> the overall
value if the letter that comes after it has a larger value, such as the <CODE>C</CODE> in <CODE>MCM</CODE>.
<P>
<B>12.13</B> Write a new version of the <CODE><A NAME="g15"></A>describe-time</CODE> procedure from Exercise
. Instead of returning a decimal number, it should behave like
this:
<P><PRE>> (describe-time 22222)
(6 HOURS 10 MINUTES 22 SECONDS)
> (describe-time 4967189641)
(1 CENTURIES 57 YEARS 20 WEEKS 6 DAYS 8 HOURS 54 MINUTES 1 SECONDS)
</PRE>
<P>Can you make the program smart about saying <CODE>1 CENTURY</CODE> instead of
<CODE>1 CENTURIES</CODE>?
<P>
<HR>
<A NAME="ft1" HREF="leap#text1">[1]</A> There's also a relationship between <CODE>(reverse 'eatles)</CODE>
and <CODE>(reverse 'beatles)</CODE>, with the extra letter <CODE>b</CODE> at the end. We
could take either of these subproblems as a starting point and end up with a
working procedure.<P>
<A NAME="ft2" HREF="leap#text2">[2]</A> Well, almost. It needs a base
case.<P>
<A NAME="ft3" HREF="leap#text3">[3]</A> What makes us confident? We
imagine that we've worked on this problem using the combining method, so
that we've written procedures like these:
<P><PRE>(define (factorial1 n)
1)
(define (factorial2 n)
(* 2 (factorial1 (- n 1))))
(define (factorial3 n)
(* 3 (factorial2 (- n 1))))
;; ...
(define (factorial842 n)
(* 842 (factorial841 (- n 1))))
</PRE>
<P>and therefore we're entitled to use those lower-numbered versions
in finding the factorial of 843. We haven't actually written them, but we
could have, and that's what justifies using them. The reason we can take
842! on faith is that 842 is smaller than 843; it's the smaller values
that we're pretending we've already written.
<P>
<A NAME="ft4" HREF="leap#text4">[4]</A> As it happens, the part in parentheses does equal the
factorial of a number, 6 itself. But expressing the solution for 6 in terms
of the solution for 6 doesn't lead to a recursive procedure; we have to
express this solution in terms of a <EM>smaller</EM> one.<P>
<A NAME="ft5" HREF="leap#text5">[5]</A> It may feel
strange that in the case of an odd-length sentence, the answer to the
recursive subproblem is the same as the answer to the original problem,
rather than a smaller answer. But remember that it's the argument, not the
return value, that has to get smaller in each recursive step.<P>
<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P>
<A HREF="../ssch11/recursion.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch13/convince-recur.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>