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/ssch13/convince-recur | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/ssch13/convince-recur')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/ssch13/convince-recur | 480 |
1 files changed, 480 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/ssch13/convince-recur b/js/games/nluqo.github.io/~bh/ssch13/convince-recur new file mode 100644 index 0000000..b505c53 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/ssch13/convince-recur @@ -0,0 +1,480 @@ +<P> + +<P><CENTER><IMG SRC="../ss-pics/mirrors.jpg" ALT="figure: mirrors"></CENTER><A NAME="mirrors"></A><P><CENTER>What's the base case? +</CENTER><P> + +<HTML> +<HEAD> +<TITLE>Simply Scheme: Introducing Computer Science ch 13: How Recursion Works</TITLE> +</HEAD> +<BODY> +<HR> +<CITE>Simply Scheme:</CITE> +<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT +<H2>Chapter 13</H2> +<H1>How Recursion Works</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/ssch13.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="../ssch12/leap.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch14/recur-patterns.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>The last two chapters were about how to write recursive procedures. This +chapter is about how to <EM>believe in</EM> recursive procedures, and about +understanding the process by which Scheme carries them out. + +<P><H2>Little People and Recursion</H2> + +<P> + +<P><A NAME="g1"></A> +The crowning achievement of the little-people model +is explaining recursion. Remember that every time you call a procedure, a +little person is hired to compute the result. If you want to know <CODE>(+ 2 (+ 3 4))</CODE>, there are two separate plus specialists involved. + +<P>When we used the combining method, it was probably clear that it's okay +for <CODE>downup3</CODE> to invoke <CODE>downup2</CODE>, and for <CODE>downup2</CODE> to invoke +<CODE>downup1</CODE>. But it probably felt like magic when we combined these +numbered procedures into a single <CODE>downup</CODE> procedure that calls <EM>itself.</EM> You may have thought, "How can <CODE>downup</CODE> do all the different +tasks at once without getting confused?" The little-people model answers +this question by showing that tasks are done by procedure <EM>invocations,</EM> not by procedures. Each little person handles one task, +even though several little people are carrying out the same procedure. The +procedure is just a set of instructions; someone has to carry out the +instructions. + +<P>So what happens when we want to know <CODE>(downup 'smile)</CODE>? We hire Donna, +a <CODE>downup</CODE> specialist, and she substitutes <CODE>smile</CODE> for <CODE>wd</CODE> in +the body of <CODE>downup</CODE>, leaving her with + +<P><PRE>(if (= (count 'smile) 1) + (se 'smile) + (se 'smile (downup (bl 'smile)) 'smile))) +</PRE> + +<P>We'll leave out the details about hiring the <CODE>if</CODE>, <CODE>=</CODE>, <CODE>count</CODE>, +and <CODE>bl</CODE> specialists in this example, so Donna ends up with + +<P><PRE>(se 'smile (downup 'smil) 'smile) +</PRE> + +<P>In order to evaluate this, Donna needs to know <CODE>(downup 'smil)</CODE>. She hires David, another <CODE>downup</CODE> specialist, and +waits for his answer. + +<P>David's <CODE>wd</CODE> is <CODE>smil</CODE>. He substitutes <CODE>smil</CODE> for <CODE>wd</CODE> in the +body of <CODE>downup</CODE>, and <EM>he</EM> gets + +<P><PRE>(if (= (count 'smil) 1) + (se 'smil) + (se 'smil (downup (bl 'smil)) 'smil))) +</PRE> + +<P>After some uninteresting work, David has + +<P><PRE>(se 'smil (downup 'smi) 'smil) +</PRE> + +<P>and he hires Dennis to compute <CODE>(downup 'smi)</CODE>. There are +now three little people, all in the middle of some <CODE>downup</CODE> computation, +and each of them is working on a different word. + +<P>Dennis substitutes <CODE>smi</CODE> for <CODE>wd</CODE>, and ends up with + +<P><PRE>(se 'smi (downup 'sm) 'smi) +</PRE> + +<P>He hires Derek to compute <CODE>(downup 'sm)</CODE>. Derek needs to +compute + +<P><PRE>(se 'sm (downup 's) 'sm) +</PRE> + +<P>Derek hires Dexter to find <CODE>downup</CODE> of <CODE>s</CODE>. Now we have to +think carefully about the substitution again. Dexter substitutes his +actual argument, <CODE>s</CODE>, for his formal parameter <CODE>wd</CODE>, and ends up +with + +<P><PRE>(if (= (count 's) 1) + (se 's) + (se 's (downup (bl 's)) 's))) +</PRE> + +<P><CODE>Count</CODE> of <CODE>s</CODE> <EM>is</EM> 1. So Dexter hires Simi, +a <CODE>sentence</CODE> specialist, who returns <CODE>(s)</CODE>. Dexter returns the same +answer to Derek. + +<P>Derek, you will recall, is trying to compute + +<P><PRE>(se 'sm (downup 's) 'sm) +</PRE> + +<P>and now he knows the value of <CODE>(downup 's)</CODE>. So he hires +Savita to compute + +<P><PRE>(se 'sm '(s) 'sm) +</PRE> + +<P>and the answer is <CODE>(sm s sm)</CODE>. Derek returns this answer to +Dennis. By the way, do you remember what question Derek was hired to +answer? Dennis wanted to know <CODE>(downup 'sm)</CODE>. The answer Derek gave +him was <CODE>(sm s sm)</CODE>, which <EM>is</EM> <CODE>downup</CODE> of <CODE>sm</CODE>. Pretty +neat, huh? +<A NAME="g2"></A> +<A NAME="g3"></A> +<A NAME="g4"></A> +<A NAME="g5"></A> +<A NAME="g6"></A> +<CENTER><IMG SRC="../ss-pics/elves.jpg" ALT="figure: elves"></CENTER> + +<P> +Dennis hires Sigrid to compute + +<P><PRE>(se 'smi '(sm s sm) 'smi) +</PRE> + +<P>and returns <CODE>(smi sm s sm smi)</CODE> to David. His answer is the +correct value of <CODE>(downup 'smi)</CODE>. David returns + +<P><PRE>(smil smi sm s sm smi smil) +</PRE> + +<P>to Donna, who has been waiting all this time to evaluate + +<P><PRE>(se 'smile (downup 'smil) 'smile) +</PRE> + +<P>Her waiting microseconds are over. She hires a <CODE>sentence</CODE> +specialist and returns + +<P><PRE>(smile smil smi sm s sm smi smil smile) +</PRE> + +<P><P> +If you have a group of friends whose names all start with "D," you can try +this out yourselves. The rules of the game are pretty simple. Remember +that each one of you can have only one single value for <CODE>wd</CODE>. Also, +only one of you is in charge of the game at any point. When you hire +somebody, that new person is in charge of the game until he or she tells you +the answer to his or her question. If some of you have names that don't +start with "D," you can be specialists in <CODE>sentence</CODE> or <CODE>butlast</CODE> +or something. Play hard, play fair, nobody hurt. + +<P> +<H2>Tracing</H2> + +<P>The little-people model explains recursion very well, as long as you're +willing to focus your attention on the job of one little person, taking the +next little person's subtask as a "black box" that you assume is carried +out correctly. Your willingness to make that assumption is a necessary step +in becoming truly comfortable with recursive programming. + +<P>Still, some people are very accustomed to a <EM>sequential</EM> model of +computing. In that model, there's only one computer, not a lot of little +people, and that one computer has to carry out one step at a time. If +you're one of those people, you may find it hard to take the subtasks on +faith. You want to know exactly what happens when! There's nothing wrong +with such healthy scientific skepticism about recursion. + +<P>If you're a sequential thinker, you can <EM>trace</EM> procedures to get +<A NAME="g7"></A> +detailed information about the sequence of events.<A NAME="text1" HREF="convince-recur#ft1">[1]</A> But if +you're happy with the way we've been talking about recursion up to now, and +if you find that this section doesn't contribute to your +understanding of recursion, don't worry about it. Our experience +shows that this way of thinking helps some people but not +everybody.<A NAME="text2" HREF="convince-recur#ft2">[2]</A> +Before we get to recursive procedures, let's just trace some nonrecursive +ones: + +<P><PRE>(define (double wd) (word wd wd)) + +> (trace double) +> (double 'frozen) +<SMALL><CODE>(double frozen) +frozenfrozen +</CODE></SMALL>FROZENFROZEN +</PRE> + +<P>The argument to <CODE>trace</CODE> specifies a procedure. When you +invoke <CODE>trace</CODE>, that procedure becomes "traced"; this means that every time +you invoke the procedure, Scheme will print out the name of the procedure +and the actual arguments. When the procedure returns a +<A NAME="g8"></A> +value, Scheme will print that value.<A NAME="text3" HREF="convince-recur#ft3">[3]</A> + +<P>Tracing isn't very interesting if we're just invoking a traced procedure +once. But look what happens when we trace a procedure that we're using +more than once: + +<P><PRE>> (double (double (double 'yum))) +<SMALL><CODE>(double yum) +yumyum +(double yumyum) +yumyumyumyum +(double yumyumyumyum) +yumyumyumyumyumyumyumyum +</CODE></SMALL> +YUMYUMYUMYUMYUMYUMYUMYUM +</PRE> + +<P>This time, there were three separate +invocations of <CODE>double</CODE>, and we saw each one as it happened. First we +<CODE>double</CODE>d <CODE>yum</CODE>, and the answer was <CODE>yumyum</CODE>. Then we <CODE>double</CODE>d <CODE>yumyum</CODE>, and so on. Finally, after we invoked <CODE>double</CODE> for +the last time, its result was printed by the read-eval-print loop. + +<P> +<P>When you're finished investigating a procedure, you can turn off tracing by +invoking <A NAME="g9"></A><CODE>untrace</CODE> with the procedure as argument: + +<P><PRE>> (untrace double) +</PRE> + +<P>Let's try tracing a recursive procedure: + +<P><PRE>(define (downup wd) + (if (= (count wd) 1) + (se wd) + (se wd (downup (bl wd)) wd))) + +> (trace downup) + +> (downup 'trace) +<SMALL><CODE>(downup trace) +| (downup trac) +| | (downup tra) +| | | (downup tr) +| | | | (downup t) +| | | | (t) +| | | (tr t tr) +| | (tra tr t tr tra) +| (trac tra tr t tr tra trac) +(trace trac tra tr t tr tra trac trace) +</CODE></SMALL>(TRACE TRAC TRA TR T TR TRA TRAC TRACE) +</PRE> + +<P>When a procedure calls itself recursively, depending on the +<A NAME="g10"></A><A NAME="g11"></A>phase of the moon,<A NAME="text4" HREF="convince-recur#ft4">[4]</A> Scheme may indent the trace display to show the levels of +procedure calling, and draw a line of vertical bars ("<CODE>|</CODE>") from a +procedure's invocation to its return value below. This is so you can look at +a procedure invocation and see what value it returned, or vice versa. + +<P>How does the trace help us understand what is going on in the recursion? +First, by reading the trace results from top to bottom, you can see +the actual sequence of events when the computer is carrying out your +Scheme program. For example, you can see that we start trying to figure +out <CODE>(downup 'trace)</CODE>; the first thing printed is the line that says +we're starting that computation. But, before we get a result from that, +four more <CODE>downup</CODE> computations have to begin. The one that begins +last finishes first, returning <CODE>(t)</CODE>; then another one returns a value; +the one that started first is the last to return. + +<P>You can also read the trace horizontally instead of vertically, focusing +on the levels of indentation. If you do this, then instead of a sequence +of independent events (such-and-such starts, such-and-such returns a value) +you see the <EM>inclusion</EM> of processes within other ones. The +smallest <CODE>downup</CODE> invocation is entirely inside the next-smallest +one, and so on. The initial invocation of <CODE>downup</CODE> includes all of +the others. + +<P>Perhaps you're thinking that <CODE>downup</CODE>'s pattern of inclusion is the only +one possible for recursive procedures. That is, perhaps you're thinking that +every invocation includes exactly one smaller invocation, and <EM>that</EM> +one includes a yet-smaller one, and so on. But actually the pattern can be +more complicated. Here's an example. The <EM><A NAME="g12"></A><A NAME="g13"></A>Fibonacci numbers</EM> are a sequence of numbers in which the first +two numbers are 1 and each number after that is the sum of the two before +it: + +<P><CENTER>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...</CENTER> +<P> (They're named after +<A NAME="g14"></A>Leonardo Pisano. You'd think they'd be called "Pisano numbers," +but Leonardo had a kind of alias, Leonardo Fibonacci, just to confuse +people.) Here's a procedure to compute the <EM>n</EM>th Fibonacci number: + +<P><PRE>(define (<A NAME="g15"></A>fib n) + (if (<= n 2) + 1 + (+ (fib (- n 1)) + (fib (- n 2))))) +</PRE> + +<P>Here's a trace of computing the fourth Fibonacci number: + +<PRE>> (fib 4) +<SMALL><CODE>(fib 4) +| (fib 2) +| 1 +| (fib 3) +| | (fib 1) +| | 1 +| | (fib 2) +| | 1 +| 2 +3 +</CODE></SMALL>3 +</PRE> + +<P>(By the way, this trace demonstrates that in the dialect of +Scheme we used, the argument subexpressions of the <CODE>+</CODE> expression in +<CODE>fib</CODE> are evaluated from right to left, because the smaller <CODE>fib</CODE> +arguments come before the larger ones in the trace.) + +<P>As you can see, we still have invocations within other invocations, but the +pattern is not as simple as in the <CODE>downup</CODE> case. If you're having +trouble making sense of this pattern, go back to thinking about the problem +in terms of little people; who hires whom? + +<P> +<P><H2>Pitfalls</H2> + +<P>Whenever you catch yourself using the words "go back" or "goes +back" in describing how some procedure works, bite your tongue. A recursive +invocation isn't a going back; it's a separate process. The model +behind "go back" is that the same little person starts over again at the +beginning of the procedure body. What actually happens is that a new little +person carries out the same procedure. It's an important difference because +when the second little person finishes, the first may still have more work +to do. + +<P>For example, when we used little people to show the working of <CODE>downup</CODE>, Dennis computes the result <CODE>(smi sm s sm smi)</CODE> and returns that +value to David; at that point, David still has work to do before returning +his own result to Donna. + +<P>The <CODE>trace</CODE> mechanism doesn't work for <A NAME="g16"></A><A NAME="g17"></A>special forms. For +example, you can't say + +<P><PRE>(trace or) +</PRE> + +<P>although you can, and often will, trace primitive procedures that +aren't special forms. + +<P><H2>Boring Exercises</H2> + +<P><B>13.1</B> Trace the <CODE>explode</CODE> procedure from page <A HREF="../ssch11/recursion.html#explodepage">there</A> and invoke + +<P><PRE>(explode 'ape) +</PRE> + +<P>How many recursive calls were there? What were the arguments to each +recursive call? Turn in a transcript showing the <CODE>trace</CODE> listing. + + +<P> +<B>13.2</B> How many <CODE>pigl</CODE>-specialist little people are involved in evaluating +the following expression? + +<P><PRE>(pigl 'throughout) +</PRE> + +<P>What are their arguments and return values, and to whom does each +give her result? + + +<P> +<B>13.3</B> Here is our first version of <CODE>downup</CODE> from Chapter 11. It +doesn't work because it has no base case. + +<P><PRE>(define (downup wd) + (se wd (downup (bl wd)) wd)) + +> (downup 'toe) +ERROR: Invalid argument to BUTLAST: "" +</PRE> + +<P>Explain what goes wrong to generate that error. In particular, why does +Scheme try to take the <CODE>butlast</CODE> of an empty word? + + +<P> +<B>13.4</B> Here is a Scheme procedure that never finishes its job: + +<P><PRE>(define (forever n) + (if (= n 0) + 1 + (+ 1 (forever n)))) +</PRE> + +<P>Explain why it doesn't give any result. (If you try to trace it, +make sure you know how to make your version of Scheme stop what it's doing +and give you another prompt.) + + +<P> +<H2>Real Exercises</H2> + +<P><B>13.5</B> It may seem strange that there is one little person per <EM>invocation</EM> +of a procedure, instead of just one little person per procedure. For +certain problems, the person-per-procedure model would work fine. + +<P>Consider, for example, this invocation of <CODE>pigl</CODE>: + +<P><PRE>> (pigl 'prawn) +AWNPRAY +</PRE> + +<P>Suppose there were only one <CODE>pigl</CODE> specialist in the computer, +named Patricia. Alonzo hires Patricia and gives her the argument <CODE>prawn</CODE>. She sees that it doesn't begin with a vowel, so she moves the first +letter to the end, gets <CODE>rawnp</CODE>, and tries to <CODE>pigl</CODE> that. Again, it +doesn't begin with a vowel, so she moves another letter to the end and gets +<CODE>awnpr</CODE>. That <EM>does</EM> begin with a vowel, so she adds an <CODE>ay</CODE>, +returning <CODE>awnpray</CODE> to Alonzo. + +<P>Nevertheless, this revised little-people model doesn't always work. Show +how it fails to explain what happens in the evaluation of + +<P><PRE>(downup 'smile) +</PRE> + + +<P> +<B>13.6</B> As part of computing <CODE>(factorial 6)</CODE>, Scheme computes <CODE>(factorial 2)</CODE> and gets the answer <CODE>2</CODE>. After Scheme gets that answer, +how does it know what to do next? + + +<P> + +<HR> +<A NAME="ft1" HREF="convince-recur#text1">[1]</A> Unfortunately, +<CODE>trace</CODE> isn't part of the Scheme standard, so it doesn't behave the same +way in every version of Scheme.<P> +<A NAME="ft2" HREF="convince-recur#text2">[2]</A> Even if tracing doesn't help you with recursion, +you'll find that it's a useful technique in debugging any procedure.<P> +<A NAME="ft3" HREF="convince-recur#text3">[3]</A> In this example the return +value was printed twice, because the procedure we traced was invoked directly +at the Scheme prompt. Its return value would have been printed once anyway, +just because that's what Scheme always does. It was printed another time +because of the tracing. In this book we've printed the trace-specific +output in smaller type and lower-case to help you understand which is what, +but of course on the actual computer you're on your own.<P> +<A NAME="ft4" HREF="convince-recur#text4">[4]</A> That's computer science slang +for "depending on a number of factors that I consider too complicated to +bother explaining" or "depending on a number of factors that I don't +understand myself." Some computer systems automatically print the phase of +the moon on program listings as an aid for programmers with +"POM-dependent" programs. What we meant in this case is that it depends +both on your version of Scheme and on the exact form of your recursive +procedure.<P> +<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P> +<A HREF="../ssch12/leap.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../ssch14/recur-patterns.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |