1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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>
|