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/part4.html | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch11/part4.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch11/part4.html | 108 |
1 files changed, 108 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> |