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