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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
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.html#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.html#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.html#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.html#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.html#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.html#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.html#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.html#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>
|