diff options
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch15/adv-recur.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch15/adv-recur.html | 553 |
1 files changed, 553 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch15/adv-recur.html b/js/games/nluqo.github.io/~bh/ssch15/adv-recur.html new file mode 100644 index 0000000..c6a3bea --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch15/adv-recur.html @@ -0,0 +1,553 @@ +<P> +<A NAME="fractal"></A> +<P><CENTER><IMG SRC="../ss-pics/fractal.jpg" ALT="figure: fractal"></CENTER><P><CENTER>Zoom in on some parts of a fractal and you'll see a miniature version +of the whole thing. +</CENTER><P> + +<HTML> +<HEAD> +<TITLE>Simply Scheme: Introducing Computer Science ch 15: Advanced Recursion</TITLE> +</HEAD> +<BODY> +<HR> +<CITE>Simply Scheme:</CITE> +<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT +<H2>Chapter 15</H2> +<H1>Advanced Recursion</H1> + +<TABLE width="100%"><TR><TD> +<IMG SRC="../simply.jpg" ALT="cover photo"> +<TD><TABLE> +<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian +Harvey</A><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew +Wright</A><BR>University of California, Santa Barbara</CITE> +<TR><TD align="right"><BR> +<TR><TD align="right"><A HREF="../pdf/ssch15.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="../ssch14/number-name.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="poker.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>By now you've had a good deal of experience with straightforward recursive +problems, and we hope you feel comfortable with them. In this chapter, we +present some more challenging problems. But the same leap of faith method +that we used for easier problems is still our basic approach. + +<P><H2>Example: <CODE>Sort</CODE></H2> + +<P>First we'll consider the example of sorting a sentence. The argument +will be any sentence; our procedure will return a sentence with the same +words in alphabetical order. + +<P><PRE>> (sort '(i wanna be your man)) +(BE I MAN WANNA YOUR) +</PRE> + +<P>We'll use the <CODE>before?</CODE> primitive to decide if one word comes before +another word alphabetically: + +<P><PRE>> (before? 'starr 'best) +#F +</PRE> + +<P>How are we going to think about this problem recursively? Suppose that +we're given a sentence to sort. A relatively easy subproblem is to find the +word that ought to come first in the sorted sentence; we'll write <CODE>earliest-word</CODE> later to do this. + +<P>Once we've found that word, we just need to put it in front of the sorted +version of the rest of the sentence. This is our leap of faith: +We're going to assume that we can already sort this smaller sentence. +The algorithm we've described is called <EM>selection</EM> sort. + +<P> +Another subproblem is to find the "rest of the sentence"—all the words +except for the earliest. But in Exercise <A HREF="../ssch14/recur-patterns.html#remonce">14.1</A> you wrote a function +<CODE>remove-once</CODE> that takes a word and a sentence and returns the sentence +with that word removed. (We don't want to use <CODE>remove</CODE>, which removes +all copies of the word, because our argument sentence might include the same +word twice.) + +<P>Let's say in Scheme what we've figured out so far: + +<P><PRE>(define (sort sent) ;; unfinished + (se (earliest-word sent) + (sort (remove-once (earliest-word sent) sent)))) +</PRE> + +<P>We need to add a base case. The smallest sentence is <CODE>()</CODE>, +which is already sorted. + +<P><PRE>(define (<A NAME="g1"></A>sort sent) + (if (empty? sent) + '() + (se (earliest-word sent) + (sort (remove-once (earliest-word sent) sent))))) +</PRE> + +<P>We have one unfinished task: finding the earliest word of the argument. + +<P><PRE>(define (<A NAME="g2"></A>earliest-word sent) + (earliest-helper (first sent) (bf sent))) + +(define (earliest-helper so-far rest) + (cond ((empty? rest) so-far) + ((before? so-far (first rest)) + (earliest-helper so-far (bf rest))) + (else (earliest-helper (first rest) (bf rest)))))<A NAME="text1" HREF="adv-recur.html#ft1">[1]</A></PRE> + +<P> + +<P>For your convenience, here's <CODE>remove-once</CODE>: +<PRE>(define (<A NAME="g3"></A>remove-once wd sent) + (cond ((empty? sent) '()) + ((equal? wd (first sent)) (bf sent)) + (else (se (first sent) (remove-once wd (bf sent)))))) +</PRE> + +<P> +<H2>Example: <CODE>From-Binary</CODE></H2> + +<P> + +<P>We want to take a word of ones and zeros, representing a +<A NAME="g4"></A><A NAME="g5"></A>binary number, and compute the numeric value that it represents. +Each binary digit (or <EM>bit</EM>) corresponds to a power of two, just as +ordinary decimal digits represent powers of ten. So the binary number 1101 +represents (1×8)+(1×4)+(0×2)+(1×1) = 13. We want to be able to say + +<P><PRE>> (from-binary 1101) +13 + +> (from-binary 111) +7 +</PRE> + + +<P>Where is the smaller, similar subproblem? Probably the most obvious thing +to try is our usual trick of dividing the argument into its <CODE>first</CODE> and +its <CODE>butfirst</CODE>. Suppose we divide the binary number <CODE>1101</CODE> that +way. We make the leap of faith by assuming that we can translate the +butfirst, <CODE>101</CODE>, into its binary value 5. What do we have to add for +the leftmost <CODE>1</CODE>? It contributes 8 to the total, because it's three +bits away from the right end of the number, so it must be multiplied by +2<SUP><SMALL>3</SMALL></SUP>. We could write this idea as follows: + +<P><PRE>(define (from-binary bits) ;; incomplete + (+ (* (first bits) (expt 2 (count (bf bits)))) + (from-binary (bf bits)))) +</PRE> + +<P>That is, we multiply the <CODE>first</CODE> bit by a power of two +depending on the number of bits remaining, then we add that +to the result of the recursive call. + +<P>As usual, we have written the algorithm for the recursive case before +figuring out the base case. But it's pretty easy; a number with no bits (an +empty word) has the value zero.<A NAME="text2" HREF="adv-recur.html#ft2">[2]</A> + +<P><PRE>(define (<A NAME="g6"></A>from-binary bits) + (if (empty? bits) + 0 + (+ (* (first bits) (expt 2 (count (bf bits)))) + (from-binary (bf bits))))) +</PRE> + +<P>Although this procedure is correct, it's worth noting that a more efficient +version can be written by dissecting the number from right to left. As +you'll see, we can then avoid the calls to <CODE>expt</CODE>, which are expensive +because we have to do more multiplication than should be necessary. + +<P>Suppose we want to find the value of the binary number <CODE>1101</CODE>. The <CODE>butlast</CODE> of this number, <CODE>110</CODE>, has the value six. To get the value of +the entire number, we double the six (because <CODE>1100</CODE> would have the value +12, just as in ordinary decimal numbers 430 is ten times 43) and then add the +rightmost bit to get 13. Here's the new version: + +<P><PRE>(define (<A NAME="g7"></A>from-binary bits) + (if (empty? bits) + 0 + (+ (* (from-binary (bl bits)) 2) + (last bits)))) +</PRE> + +<P>This version may look a little unusual. We usually combine the value +returned by the recursive call with some function of the current element. +This time, we are combining the current element itself with a function of +the recursive return value. You may want to trace this procedure to see how +the intermediate return values contribute to the final result. + +<P><H2>Example: <CODE>Mergesort</CODE></H2> + +<P>Let's go back to the problem of sorting a sentence. It turns out that +sorting one element at a time, as in selection sort, isn't the fastest +possible approach. One of the fastest sorting algorithms is called <EM>mergesort,</EM> and it works like this: In order to mergesort a +sentence, divide the sentence into two equal halves and recursively sort +each half. Then take the two sorted subsentences and <EM>merge</EM> them +together, that is, create one long sorted sentence that contains all the words +of the two halves. The base case is that an empty sentence or a one-word +sentence is already sorted. + +<P><PRE>(define (<A NAME="g8"></A>mergesort sent) + (if (<= (count sent) 1) + sent + (merge (mergesort (one-half sent)) + (mergesort (other-half sent))))) +</PRE> + +<P>The leap of faith here is the idea that we can magically <CODE>mergesort</CODE> +the halves of the sentence. If you try to trace this through step by step, +or wonder exactly what happens at what time, then this algorithm may be very +confusing. But if you just <EM>believe</EM> that the recursive calls will do +exactly the right thing, then it's much easier to understand this program. +The key point is that if the two smaller pieces have already been sorted, +it's pretty easy to merge them while keeping the result in order. + +<P>We still need some helper procedures. You wrote <CODE>merge</CODE> in Exercise +<A HREF="../ssch14/recur-patterns.html#mergeex">14.15</A>. It uses the following technique: Compare the first words of the +two sentences. Let's say the first word of the sentence on the left is +smaller. Then the first word of the return value is the first word of the +sentence on the left. The rest of the return value comes from recursively +merging the <CODE>butfirst</CODE> of the left sentence with the entire right +sentence. (It's precisely the opposite of this if the first word of the +other sentence is smaller.) + +<P><PRE>(define (<A NAME="g9"></A>merge left right) + (cond ((empty? left) right) + ((empty? right) left) + ((before? (first left) (first right)) + (se (first left) (merge (bf left) right))) + (else (se (first right) (merge left (bf right)))))) +</PRE> + +<P>Now we have to write <CODE>one-half</CODE> and <CODE>other-half</CODE>. One of the +easiest ways to do this is to have <CODE>one-half</CODE> return the elements in +odd-numbered positions, and have <CODE>other-half</CODE> return the elements in +even-numbered positions. These are the same as the procedures <CODE>odds</CODE> +(from Exercise <A HREF="../ssch14/recur-patterns.html#exodds">14.4</A>) and <CODE>evens</CODE> (from Chapter 12). + +<P><PRE>(define (<A NAME="g10"></A>one-half sent) + (if (<= (count sent) 1) + sent + (se (first sent) (one-half (bf (bf sent)))))) + +(define (<A NAME="g11"></A>other-half sent) + (if (<= (count sent) 1) + '() + (se (first (bf sent)) (other-half (bf (bf sent)))))) +</PRE> + +<P><H2>Example: <CODE>Subsets</CODE></H2> + +<P>We're now going to attack a much harder problem. We want to know all the +subsets of the letters of a word—that is, words that can be formed +from the original word by crossing out some (maybe zero) of the letters. For +example, if we start with a short word like <CODE>rat</CODE>, the subsets are <CODE>r</CODE>, <CODE>a</CODE>, <CODE>t</CODE>, <CODE>ra</CODE>, <CODE>rt</CODE>, <CODE>at</CODE>, <CODE>rat</CODE>, and the empty +word (<CODE>""</CODE>). As the word gets longer, the number of subsets gets bigger +very quickly.<A NAME="text3" HREF="adv-recur.html#ft3">[3]</A> + +<P>As with many problems about words, we'll try assuming that we can find the +subsets of the <CODE>butfirst</CODE> of our word. In other words, we're hoping to +find a solution that will include an expression like + +<P><PRE>(subsets (bf wd)) +</PRE> + +<P>Let's actually take a four-letter word and look at its subsets. We'll pick +<CODE>brat</CODE>, because we already know the subsets of its <CODE>butfirst</CODE>. Here +are the subsets of <CODE>brat</CODE>: + +<P><PRE>"" b r a t br ba bt ra rt at bra brt bat rat brat +</PRE> + +<P>You might notice that many of these subsets are also subsets of <CODE>rat</CODE>. +In fact, if you think about it, <EM>all</EM> of the subsets of <CODE>rat</CODE> are +also subsets of <CODE>brat</CODE>. So the words in <CODE>(subsets 'rat)</CODE> are some +of the words we need for <CODE>(subsets 'brat)</CODE>. + +<P>Let's separate those out and look at the ones left over: + +<P><TABLE><TR><TD><CODE>rat</CODE> subsets: +<TD> <CODE>""<TD> <CODE>r</CODE> +<TD> <CODE>a</CODE><TD> <CODE>t</CODE> +<TD> <CODE>ra</CODE><TD> <CODE>rt</CODE> +<TD> <CODE>at</CODE><TD> <CODE></CODE><TD> <CODE>rat</CODE> +<TR><TD>others: +<TD> <CODE>b</CODE><TD> <CODE>br</CODE> +<TD> <CODE>ba</CODE><TD> <CODE>bt</CODE> +<TD> <CODE>bra</CODE><TD> <CODE>brt</CODE> +<TD> <CODE>bat</CODE><TD> <CODE></CODE><TD> <CODE>brat</CODE> +</TABLE> + + +<P><P> +Right about now you're probably thinking, "They've pulled a rabbit out of a +hat, the way my math teacher always does." The words that aren't subsets of +<CODE>rat</CODE> all start with <CODE>b</CODE>, followed by something that <EM>is</EM> a +subset of <CODE>rat</CODE>. You may be thinking that you never would have thought +of that yourself. But we're just following the method: Look at the smaller +case and see how it fits into the original problem. It's not so different +from what happened with <CODE>downup</CODE>. + +<P>Now all we have to do is figure out how to say in Scheme, "Put a <CODE>b</CODE> +in front of every word in this sentence." This is a straightforward +example of the <CODE>every</CODE> pattern: + +<P><PRE>(define (<A NAME="g12"></A>prepend-every letter sent) + (if (empty? sent) + '() + (se (word letter (first sent)) + (prepend-every letter (bf sent))))) +</PRE> + +<P>The way we'll use this in <CODE>(subsets 'brat)</CODE> is + +<P><PRE>(prepend-every 'b (subsets 'rat)) +</PRE> + +<P>Of course in the general case we won't have <CODE>b</CODE> and <CODE>rat</CODE> in our +program, but instead will refer to the formal parameter: + +<P><PRE>(define (subsets wd) ;; first version + (se (subsets (bf wd)) + (prepend-every (first wd) (subsets (bf wd))))) +</PRE> + +<P>We still need a base case. By now you're accustomed to the idea of using an +empty word as the base case. It may be strange to think of the empty word +as a set in the first place, let alone to try to find its subsets. But a +set of zero elements is a perfectly good set, and it's the smallest one +possible. + +<P>The empty set has only one subset, the empty set itself. What should +<CODE>subsets</CODE> of the empty word return? It's easy to make a mistake here +and return the empty word itself. But we want <CODE>subsets</CODE> to return a +sentence, containing all the subsets, and we should stick with returning a +sentence even in the simple case.<A NAME="text4" HREF="adv-recur.html#ft4">[4]</A> (This mistake would come from not thinking about +the <EM>range</EM> of our function, which is sentences. This is why we put +so much effort into learning about domains and ranges in Chapter +2.) So we'll return a sentence containing one (empty) word to +represent the one subset. + +<P><PRE>(define (subsets wd) ;; second version + (if (empty? wd) + (se "") + (se (subsets (bf wd)) + (prepend-every (first wd) (subsets (bf wd)))))) +</PRE> + +<P>This program is entirely correct. Because it uses two identical recursive +calls, however, it's a lot slower than necessary. We can use <CODE>let</CODE> to +do the recursive subproblem only once:<A NAME="text5" HREF="adv-recur.html#ft5">[5]</A> + +<P><PRE>(define (<A NAME="g13"></A>subsets wd) + (if (empty? wd) + (se "") + (let ((smaller (subsets (bf wd)))) + (se smaller + (prepend-every (first wd) smaller))))) +</PRE> + +<P><H2>Pitfalls</H2> + +<P>We've already mentioned the need to be careful about the value returned +in the base case. The <CODE>subsets</CODE> procedure is particularly error-prone +because the correct value, a sentence containing the empty word, is quite +unusual. An empty subset isn't the same as no subsets at all! + +<P>Sometimes you write a recursive procedure with a correct recursive case +and a reasonable base case, but the program still doesn't work. The trouble +may be that the base case doesn't quite catch all of the ways in which the +problem can get smaller. A second base case may be needed. For example, in +<CODE>mergesort</CODE>, why did we write the following line? + +<P><PRE>(<= (count sent) 1) +</PRE> + +<P>This tests for two base cases, empty sentences and one-word +sentences, whereas in most other examples the base case is just an empty +sentence. Suppose the base case test were <CODE>(empty? sent)</CODE> and suppose we +invoke <CODE>mergesort</CODE> with a one-word sentence, <CODE>(test)</CODE>. We would end +up trying to compute the expression + +<P><PRE>(merge (mergesort (one-half '(test))) + (mergesort (other-half '(test)))) +</PRE> + +<P>If you look back at the definitions of <CODE>one-half</CODE> and +<CODE>other-half</CODE>, you'll see that this is equivalent to + +<P><PRE>(merge (mergesort '(test)) (mergesort '())) +</PRE> + +<P>The first argument to <CODE>merge</CODE> is the same expression we +started with! Here is a situation in which the problem doesn't get smaller +in a recursive call. Although we've been trying to avoid complicated base +cases, in this situation a straightforward base case isn't enough. To avoid +an infinite recursion, we must have two base cases. + +<P>Another example is the <CODE>fib</CODE> procedure from Chapter . Suppose +it were defined like this: + +<P><PRE>(define (fib n) ;; wrong! + (if (= n 1) + 1 + (+ (fib (- n 1)) + (fib (- n 2))))) +</PRE> + +<P>It would be easy to make this mistake, because everybody knows +that in a recursion dealing with numbers, the base case is the smallest +possible number. But in <CODE>fib</CODE>, each computation depends on <EM>two</EM> +smaller values, and we discover that we need two base cases. + +<P>The technique of recursion is often used to do something repetitively, +but don't get the idea that the word "recursion" <EM>means</EM> +repetition. Recursion is a technique in which a procedure invokes itself. +We do use recursion to solve repetitive problems, but don't confuse the +method with the ends it achieves. In particular, if you've programmed in +other languages that have special-purpose looping mechanisms (the ones +with names like <CODE>for</CODE> and <CODE>while</CODE>), those aren't recursive. +Conversely, not every recursive procedure carries out a repetition. + +<P> +<H2>Exercises</H2> + +<P><B>15.1</B> Write a procedure <CODE>to-binary</CODE>: + +<P><PRE>> (to-binary 9) +1001 + +> (to-binary 23) +10111 +</PRE> + +<P> +<B>15.2</B> A "palindrome" is a sentence that reads the same backward as forward. +Write a predicate <CODE>palindrome?</CODE> that takes a sentence as argument and +decides whether it is a palindrome. For example: + +<P><PRE>> (palindrome? '(flee to me remote elf)) +#T + +> (palindrome? '(flee to me remote control)) +#F +</PRE> + +<P>Do not reverse any words or sentences in your solution. + + +<P> +<B>15.3</B> Write a procedure <CODE><A NAME="g14"></A>substrings</CODE> that takes a word as its +argument. It should return a sentence containing all of the substrings of +the argument. A <EM>substring</EM> is a subset whose letters come +consecutively in the original word. For example, the word <CODE>bat</CODE> is a +subset, but <EM>not</EM> a substring, of <CODE>brat</CODE>. +<A NAME="substrings"></A> + + +<P> +<B>15.4</B> Write a predicate procedure <CODE><A NAME="g15"></A>substring?</CODE> that takes two words as +arguments and returns <CODE>#t</CODE> if and only if the first word is a substring +of the second. (See Exercise <A HREF="adv-recur.html#substrings">15.3</A> for the definition of a +substring.) + +<P>Be careful about cases in which you encounter a "false start," like this: + +<P><PRE>> (substring? 'ssip 'mississippi) +#T +</PRE> + +<P>and also about subsets that don't appear as consecutive letters +in the second word: + +<P><PRE>> (substring? 'misip 'mississippi) +#F +</PRE> + +<P> +<B>15.5</B> Suppose you have a phone number, such as 223-5766, and you'd like to figure out +a clever way to spell it in letters for your friends to remember. Each +digit corresponds to three possible letters. For example, the digit 2 +corresponds to the letters A, B, and C. Write a procedure that takes a +number as argument and returns a sentence of all the possible spellings: + +<P><PRE>> (<A NAME="g16"></A>phone-spell 2235766) +(AADJPMM AADJPMN …CCFLSOO) +</PRE> + +<P>(We're not showing you all 2187 words in this sentence.) You may +assume there are no zeros or ones in the number, since those don't have +letters. + +<P>Hint: This problem has a lot in common with the subsets example. + + +<P> +<B>15.6</B> Let's say a gladiator kills a roach. If we want to talk about the roach, we +say "the roach the gladiator killed." But if we want to talk about the +gladiator, we say "the gladiator that killed the roach." + +<P>People are pretty good at understanding even rather long sentences +as long as they're straightforward: "This is the farmer who kept +the cock that waked the priest that married the man that kissed the +maiden that milked the cow that tossed the dog that worried the cat +that killed the rat that ate the malt that lay in the house that +Jack built." But even a short <EM>nested</EM> sentence is +confusing: "This is the rat the cat the dog worried killed." +Which rat was that? + +<P>Write a procedure <CODE><A NAME="g17"></A>unscramble</CODE> that takes a nested +sentence as argument and returns a straightforward sentence about +the same cast of characters: + +<P><PRE>> (unscramble '(this is the roach the gladiator killed)) +(THIS IS THE GLADIATOR THAT KILLED THE ROACH) + +> (unscramble '(this is the rat the cat the dog the boy the + girl saw owned chased bit)) +(THIS IS THE GIRL THAT SAW THE BOY THAT OWNED THE DOG THAT + CHASED THE CAT THAT BIT THE RAT) +</PRE> + +<P>You may assume that the argument has exactly the structure +of these examples, with no special cases like "that lay <EM>in</EM> the +house" or "that <EM>Jack</EM> built." + + +<P> + +<HR> +<A NAME="ft1" HREF="adv-recur.html#text1">[1]</A> If you've read Part III, you might instead want to use <CODE>accumulate</CODE> for this purpose: + +<P><PRE>(define earliest-word sent) + (accumulate (lambda (wd1 wd2) (if (before? wd1 wd2) wd1 wd2)) + sent)) +</PRE><P> +<A NAME="ft2" HREF="adv-recur.html#text2">[2]</A> A more straightforward base case +would be a one-bit number, but we've reduced that to this more elegant base +case, following the principle we discussed on page <A HREF="../ssch12/leap.html#basecasereduce">there</A>.<P> +<A NAME="ft3" HREF="adv-recur.html#text3">[3]</A> Try writing down all the subsets of a five-letter word +if you don't believe us.<P> +<A NAME="ft4" HREF="adv-recur.html#text4">[4]</A> We discussed this point in a +pitfall in Chapter 12.<P> +<A NAME="ft5" HREF="adv-recur.html#text5">[5]</A> How come we're worrying about +efficiency all of a sudden? We really <EM>did</EM> pull this out of a hat. +The thing is, it's a <EM>lot</EM> slower without the <CODE>let</CODE>. Adding one +letter to the length of a word doubles the time required to find its +subsets; adding 10 letters multiplies the time by about 1000.<P> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="../ssch14/number-name.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="poker.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |