diff options
| author | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
| commit | 562a9a52d599d9a05f871404050968a5fd282640 (patch) | |
| tree | 7d3305c1252c043bfe246ccc7deff0056aa6b5ab /js/games/nluqo.github.io/~bh/ssch12 | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch12')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch12/leap | 860 | ||||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch12/leap.html | 860 | ||||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch12/math1.gif | bin | 0 -> 5802 bytes |
3 files changed, 1720 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch12/leap b/js/games/nluqo.github.io/~bh/ssch12/leap new file mode 100644 index 0000000..7ed6d0e --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch12/leap @@ -0,0 +1,860 @@ +<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> diff --git a/js/games/nluqo.github.io/~bh/ssch12/leap.html b/js/games/nluqo.github.io/~bh/ssch12/leap.html new file mode 100644 index 0000000..298234d --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch12/leap.html @@ -0,0 +1,860 @@ +<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.html#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.html#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.html#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.html#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.html#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.html#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.html#text2">[2]</A> Well, almost. It needs a base +case.<P> +<A NAME="ft3" HREF="leap.html#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.html#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.html#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> diff --git a/js/games/nluqo.github.io/~bh/ssch12/math1.gif b/js/games/nluqo.github.io/~bh/ssch12/math1.gif new file mode 100644 index 0000000..a16c1aa --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch12/math1.gif Binary files differ |
