<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>