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
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
|
<HTML>
<HEAD>
<TITLE>Computer Science Logo Style vol 1 ch 7: Introduction to Recursion</TITLE>
</HEAD>
<BODY>
<CITE>Computer Science Logo Style</CITE> volume 1:
<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT
<H1>Introduction to Recursion</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../csls1.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"><BR>
<TR><TD align="right"><A HREF="../pdf/v1ch07.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../v1-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="../v1ch6/v1ch6.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v1ch8/v1ch8.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-1">MIT
Press web page for Computer Science Logo Style</A>
</TABLE></TABLE>
<HR>
<P>
My goal in this chapter is to write a procedure named <CODE>downup</CODE>
that behaves like this:
<PRE>
? <U>downup "hello</U>
hello
hell
hel
he
h
he
hel
hell
hello
? <U>downup "goodbye</U>
goodbye
goodby
goodb
good
goo
go
g
go
goo
good
goodb
goodby
goodbye
</PRE>
<P>
The programming techniques we've used so far in this book
don't allow an elegant solution to this problem. We'll use a
new technique called <EM>recursion:</EM> writing a procedure that uses
<EM>itself</EM> as a subprocedure.
<P>
We're going to solve this problem using recursion. It turns out that the
idea of recursion is both very powerful--we can solve a <EM>lot</EM> of
problems using it--and rather tricky to understand. That's why I'm going
to explain recursion several different ways in the coming chapters. Even
after you understand one of them, you'll probably find that thinking about
recursion from another point of view enriches your ability to use this idea.
The explanation in this chapter is based on the <EM>combining method.</EM>
<H2>Starting Small</H2>
<P>
My own favorite way to understand recursion is based on the general
problem-solving strategy of solving a complicated problem by starting
with a simpler version. To solve the <CODE>downup</CODE> problem, I'll start
by solving this simpler version: write a <CODE>downup</CODE> procedure that
works only for a single-character input word. (You can't get much
simpler than that!) Here's my solution:
<PRE>
to downup1 :word
print :word
end
? <U>downup1 "j</U>
j
</PRE>
<P>
See how well it works?
<H2>Building Up</H2>
<P>
Of course, <CODE>downup1</CODE> won't work at all if you give it an input
longer than one character. You may not think this was such a big
step. But bear with me. Next I'll write a procedure that acts like
<CODE>downup</CODE> when you give it a two-letter input word:
<PRE>
to downup2 :word
print :word
print butlast :word
print :word
end
? <U>downup2 "it</U>
it
i
it
</PRE>
<P>
We could keep this up for longer and longer input words, but each procedure
gets more and more complicated. Here's <CODE>downup3</CODE>:
<PRE>
to downup3 :word
print :word
print butlast :word
print butlast butlast :word
print butlast :word
print :word
end
</PRE>
<P>
» How many <CODE>print</CODE> instructions would I need to write <CODE>downup4</CODE>
this way? How many would I need for <CODE>downup20</CODE>?
<P>
Luckily there's an easier way. Look at the result of invoking <CODE>downup3</CODE>:
<PRE>
? <U>downup3 "dot</U>
dot
<TABLE border="5" rules="none" frame="box" noshade><TR><TD>do
<TR><TD>d
<TR><TD>do</TABLE>dot
</PRE>
<P>
The trick is to recognize that the boxed lines are what we'd get by invoking
<CODE>downup2</CODE> with the word <CODE>do</CODE> as input. So we can find
the instructions in <CODE>downup3</CODE> that print those three lines and
replace them with one instruction that calls <CODE>downup2</CODE>:
<PRE>
to downup3 :word
print :word
<U>downup2 butlast :word</U>
print :word
end
</PRE>
<P>
You might have to think a moment to work out where the
<CODE>butlast</CODE> came from, but consider
that we're given the word <CODE>dot</CODE> and we
want the word <CODE>do</CODE>.
<P>
Once we've had this idea, it's easy to extend it to longer words:
<PRE>
to downup4 :word
print :word
downup3 butlast :word
print :word
end
to downup5 :word
print :word
downup4 butlast :word
print :word
end
</PRE>
<P>
» Can you rewrite <CODE>downup2</CODE> so that it looks like these others?
<P>
» Before going on, make sure you really understand these procedures by
answering these questions: What happens if you use one of these numbered
versions of <CODE>downup</CODE> with an input that is too long? What if the input
is too short?
<H2>Generalizing the Pattern</H2>
<P>
We're now in good shape as long as we want to <CODE>downup</CODE> short
words. We can pick the right version of <CODE>downup</CODE> for the length
of the word we have in mind:
<PRE>
? <U>downup5 "hello</U>
hello
hell
hel
he
h
he
hel
hell
hello
? <U>downup7 "goodbye</U>
goodbye
goodby
goodb
good
goo
go
g
go
goo
good
goodb
goodby
goodbye
</PRE>
<P>
Having to count the number of characters in the word is a
little unaesthetic, but we could even have the computer do that for us:
<PRE>
to downup :word
if equalp count :word 1 [downup1 :word]
if equalp count :word 2 [downup2 :word]
if equalp count :word 3 [downup3 :word]
if equalp count :word 4 [downup4 :word]
if equalp count :word 5 [downup5 :word]
if equalp count :word 6 [downup6 :word]
if equalp count :word 7 [downup7 :word]
end
</PRE>
<P>
There's only one problem. What if we want to be able to say
<PRE>
downup "antidisestablishmentarianism
</PRE>
<P>
You wouldn't want to have to type in separate versions of
<CODE>downup</CODE> all the way up to <CODE>downup28</CODE>!
<P>
What I hope you're tempted to do is to take advantage of the
similarity of all the numbered <CODE>downup</CODE> procedures by combining
them into a single procedure that looks like this:
<PRE>
to downup :word
print :word
downup butlast :word
print :word
end
</PRE>
<P>
(Remember that Logo's <CODE>to</CODE> command won't let you
redefine <CODE>downup</CODE> if you've already typed in my earlier version
with all the <CODE>if</CODE> instruction lines. Before you can type in the
new version, you have to <CODE>erase</CODE> the old one.)
<P>
Compare this version of <CODE>downup</CODE> with one of the numbered
procedures like <CODE>downup5</CODE>. Do you see that this combined version
should work just as well, if all the numbered
<CODE>downup</CODE> procedures are identical except for the numbers in the
procedure names?
Convince yourself that that makes sense.
<P>
» Okay, now try it.
<H2>What Went Wrong?</H2>
<P>
You probably saw something like this:
<PRE>
? <U>downup "hello</U>
hello
hell
hel
he
h
butlast doesn't like as input in downup
</PRE>
<P>
There's nothing wrong with the reasoning I used in the last section.
If all the numbered <CODE>downup</CODE> procedures are identical except for
the numbers, it should work to replace them all with a single
procedure following the same pattern.
<P>
The trouble is that the numbered <CODE>downup</CODE> procedures
<EM>aren't</EM> quite
all identical. The exception is <CODE>downup1</CODE>. If it
were like the others, it would look like this:
<PRE>
to downup1 :word
print :word
<U>downup0 butlast :word</U>
<U>print :word</U>
end
</PRE>
<P>
Review the way the numbered <CODE>downup</CODE>s work to make sure
you understand why <CODE>downup1</CODE> is different. Here's what happens
when you invoke one of the numbered versions:
<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch7/downup.gif" ALT="<P>figure: downup"></CENTER>
<P>
In this chart, instructions within a particular procedure
are indented the same amount. For example, the lines
<CODE>print "hello</CODE> and
<CODE>downup4 "hell</CODE> are part of <CODE>downup5</CODE>, as is
the line <CODE>print "hello</CODE> at the very end of the chart. The lines
in between are indented more because they're part of <CODE>downup4</CODE>
and its subprocedures.
<P>
(By the way, the lines in the chart don't show actual instructions in
the procedure definitions. Otherwise all the <CODE>print</CODE> lines would
say <CODE>print :word</CODE> instead of showing actual words. In the chart
I've already evaluated the inputs to the commands.)
<P>
The point of the chart is that <CODE>downup1</CODE> has to be special because
it marks the end of the "down" part of the problem and the
beginning of the "up" part. <CODE>downup1</CODE> doesn't invoke a
lower-numbered <CODE>downup</CODE> subprocedure because there's no smaller
piece of the word to print.
<P>
» Okay, Logo knows when to stop the "down" part of the program
because <CODE>downup1</CODE> is different from the other procedures.
Question: How does Logo know when to stop the "up" part of the
program? Why doesn't <CODE>downup5</CODE>, in this example, have to be
written differently from the others?
<H2>The Stop Rule</H2>
<P>
Our attempt to write a completely general <CODE>downup</CODE> procedure has
run into trouble because we have to distinguish two cases: the special
case in which the input word contains only one character and the
general case for longer input words. We can use <CODE>ifelse</CODE> to
distinguish the two cases:
<PRE>
to downup :word
ifelse equalp count :word 1 [downup.one :word] [downup.many :word]
end
to downup.one :word
print :word
end
to downup.many :word
print :word
downup butlast :word
print :word
end
</PRE>
<P>
You'll find that this version of the <CODE>downup</CODE> program actually
works correctly.
Subprocedure <CODE>downup.one</CODE> is exactly like the
old <CODE>downup1</CODE>, while <CODE>downup.many</CODE> is like the version
of <CODE>downup</CODE> that didn't work.
<P>
It's possible to use the same general idea, however--distinguishing
the special case of a one-letter word--without having
to set up this three-procedure structure. Instead we can take
advantage of the fact that <CODE>downup.one</CODE>'s single instruction is
the same as the first instruction of <CODE>downup.many</CODE>; we can use a
single procedure that <CODE>stop</CODE>s early if appropriate.
<PRE>
to downup :word
print :word
if equalp count :word 1 [stop]
downup butlast :word
print :word
end
</PRE>
<P>
The <CODE>if</CODE> instruction in this final version of
<CODE>downup</CODE> is called a <EM>stop rule.</EM>
<P>
<CODE>Downup</CODE> illustrates the usual pattern of a recursive procedure.
There are three kinds of instructions within its definition: (1) There
are the ordinary instructions that carry out the work of the
procedure for a particular value of the input, in this case the
<CODE>print</CODE> instructions. (2) There is at least one
<EM>recursive call,</EM>
an instruction that invokes the same procedure with a smaller input.
(3) There is a stop rule, which prevents the recursive invocation when
the input is too small.
<P>
It's important to understand that the stop rule always comes
<EM>before</EM> the recursive call or calls. One of the common mistakes
made by programmers who are just learning about recursion is to think
this way: "The stop rule <EM>ends</EM> the program, so it belongs at the
<EM>end</EM> of the procedure." The right way to think about it is
that the purpose of the stop rule is to stop the innermost invocation
of the procedure <EM>before</EM> it has a chance to invoke itself
recursively, so the stop rule must come <EM>before</EM> the recursive call.
<H2>Local Variables</H2>
<P>
When you're thinking about a recursive procedure, it's especially
important to remember that each invocation of a procedure has its own
local variables. It's possible to get confused about this
because, of course, if a procedure invokes itself as a subprocedure,
each invocation uses the same <EM>names</EM> for local variables. For
example, each invocation of <CODE>downup</CODE> has a local variable (its
input) named <CODE>word</CODE>. But each invocation has a
<EM>separate</EM> input variable.
<P>
It's hard to talk about different invocations in the abstract. So
let's look back at the version of the program in which each invocation
had a different procedure
name: <CODE>downup1</CODE>, <CODE>downup2</CODE>, and so on.
<P>
If you type the instruction
<PRE>
downup5 "hello
</PRE>
<P>
the procedure <CODE>downup5</CODE> is invoked, with the word
<CODE>hello</CODE> as
its input. <CODE>Downup5</CODE> has a local variable named
<CODE>word</CODE>, which
contains <CODE>hello</CODE> as its value. The first instruction
in <CODE>downup5</CODE> is
<PRE>
print :word
</PRE>
<P>
Since <CODE>:word</CODE> is <CODE>hello</CODE>, this instruction prints
<CODE>hello</CODE>. The next instruction is
<PRE>
downup4 butlast :word
</PRE>
<P>
This instruction invokes procedure <CODE>downup4</CODE> with the
word <CODE>hell</CODE>
(the <CODE>butlast</CODE> of <CODE>hello</CODE>) as input.
<CODE>Downup4</CODE> has a local
variable that is also named <CODE>word</CODE>. The
value of <EM>that</EM> variable is the word <CODE>hell</CODE>.
<P>
At this point there are two separate variables, both named
<CODE>word</CODE>. <CODE>Downup5</CODE>'s <CODE>word</CODE> contains
<CODE>hello</CODE>; <CODE>downup4</CODE>'s <CODE>word</CODE> contains
<CODE>hell</CODE>. I won't go through all the details of how
<CODE>downup4</CODE> invokes <CODE>downup3</CODE> and so on. But eventually
<CODE>downup4</CODE> finishes its task, and <CODE>downup5</CODE> continues
with its final instruction, which is
<PRE>
print :word
</PRE>
<P>
Even though different values have been assigned to variables named
<CODE>word</CODE> in the interim, <EM>this</EM> variable named
<CODE>word</CODE> (the one that is local to <CODE>downup5</CODE>) still has
its original value, <CODE>hello</CODE>. So that's what's printed.
<P>
In the recursive version of the program exactly the same thing
happens about local variables. It's a little harder to describe,
because all the procedure invocations are invocations of the same
procedure, <CODE>downup</CODE>. So I can't say things like "the variable
<CODE>word</CODE> that belongs to <CODE>downup4</CODE>"; instead, you have to
think about "the variable named <CODE>word</CODE> that belongs to the
second invocation of <CODE>downup</CODE>." But even though there is only
one <EM>procedure</EM> involved, there are still five procedure
<EM>invocations,</EM> each with its own local variable named <CODE>word</CODE>.
<H2>More Examples</H2>
<P>
» Before I go on to show you another example of a recursive procedure,
you might try to write <CODE>down</CODE> and <CODE>up</CODE>, which should work like
this:
<PRE>
? <U>down "hello</U>
hello
hell
hel
he
h
? <U>up "hello</U>
h
he
hel
hell
hello
</PRE>
<P>
As a start, notice that there are two <CODE>print</CODE>
instructions in <CODE>downup</CODE> and that one of them does the "down"
half and the other does the "up" half. But you'll find that just
eliminating one of the <CODE>print</CODE>s for <CODE>down</CODE> and the other for
<CODE>up</CODE> doesn't <EM>quite</EM> work.
<P>
After you've finished <CODE>down</CODE> and <CODE>up</CODE>, come back here for a
discussion of a similar project, which I call <CODE>inout</CODE>:
<PRE>
? <U>inout "hello</U>
hello
ello
llo
lo
o
lo
llo
ello
hello
</PRE>
<P>
At first glance <CODE>inout</CODE> looks just like <CODE>downup</CODE>,
except that it uses the <CODE>butfirst</CODE> of its input instead of the
<CODE>butlast</CODE>. <CODE>Inout</CODE> is somewhat more complicated than
<CODE>downup</CODE>, however, because it has to print spaces before some of the words
in order to line up the rightmost letters. <CODE>Downup</CODE> lined up the
leftmost letters, which is easy.
<P>
Suppose we start, as we did for <CODE>downup</CODE>, with a version that only
works for single-letter words:
<PRE>
to inout1 :word
print :word
end
</PRE>
<P>
But we can't quite use <CODE>inout1</CODE> as a subprocedure of
<CODE>inout2</CODE>, as we did in the <CODE>downup</CODE> problem. Instead we need
a different version of <CODE>inout1</CODE>, which types a space before its
input:
<PRE>
to inout2 :word
print :word
inout2.1 butfirst :word
print :word
end
to inout2.1 :word
type "| | ; a word containing a space
print :word
end
</PRE>
<P>
<CODE>Type</CODE> is a command, which requires one input. The
input can be any datum. <CODE>Type</CODE> prints its input, like
<CODE>print</CODE>, but does not move the cursor to a new line afterward. The
cursor remains right after the printed datum, so the next <CODE>print</CODE>
or <CODE>type</CODE> command will continue on the same line.
<P>
We need another specific case or two before a general pattern will
become apparent. Here is the version for three-letter words:
<PRE>
to inout3 :word
print :word
inout3.2 butfirst :word
print :word
end
to inout3.2 :word
type "| |
print :word
inout3.1 butfirst :word
type "| |
print :word
end
to inout3.1 :word
repeat 2 [type "| |]
print :word
end
</PRE>
<P>
Convince yourself that each of these procedures types the
right number of spaces before its input word.
<P>
Here is one final example, the version for four-letter words:
<PRE>
to inout4 :word
print :word
inout4.3 butfirst :word
print :word
end
to inout4.3 :word
type "| |
print :word
inout4.2 butfirst :word
type "| |
print :word
end
to inout4.2 :word
repeat 2 [type "| |]
print :word
inout4.1 butfirst :word
repeat 2 [type "| |]
print :word
end
to inout4.1 :word
repeat 3 [type "| |]
print :word
end
</PRE>
<P>
» Try this out and try writing <CODE>inout5</CODE> along the same lines.
<P>
How can we find a common pattern that will combine the elements of
all these procedures? It will have to look something like this:
<PRE>
to inout :word
repeat <U>something</U> [type "| |]
print :word
if <U>something</U> [stop]
inout butfirst :word
repeat <U>something</U> [type "| |]
print :word
end
</PRE>
<P>
This is not a finished procedure because we haven't figured
out how to fill the blanks. First I should remark that the stop rule
is where it is, after the first <CODE>print</CODE>, because that's how far the
innermost procedures (<CODE>inout2.1</CODE>, <CODE>inout3.1</CODE>, and
<CODE>inout4.1</CODE>) get. They type some spaces, print the input word, and
that's all.
<P>
Another thing to remark is that the first input to the <CODE>repeat</CODE>
commands in this general procedure will sometimes be zero, because the
outermost procedures (<CODE>inout2</CODE>, <CODE>inout3</CODE>, and
<CODE>inout4</CODE>) don't type any spaces at all. Each subprocedure types
one more space than its superprocedure. For example, <CODE>inout4</CODE>
types no spaces. Its subprocedure <CODE>inout4.3</CODE> types one space.
<CODE>inout4.3</CODE>'s subprocedure <CODE>inout4.2</CODE> types two
spaces. Finally, <CODE>inout4.2</CODE>'s subprocedure <CODE>inout4.1</CODE>
types three spaces.
<P>
In order to vary the number of spaces in this way, the solution is to
use another input that will have this number as its value. We can
call it <CODE>spaces</CODE>. The procedure will then look like this:
<PRE>
to inout :word :spaces
repeat :spaces [type "| |]
print :word
if equalp count :word 1 [stop]
inout (butfirst :word) (:spaces+1)
repeat :spaces [type "| |]
print :word
end
? <U>inout "hello 0</U>
hello
ello
llo
lo
o
lo
llo
ello
hello
</PRE>
<P>
Notice that, when we use <CODE>inout</CODE>, we have to give it a
zero as its second input. We could eliminate this annoyance by
writing a new <CODE>inout</CODE> that invokes this one as a subprocedure:
<PRE>
to inout :word
inout.sub :word 0
end
to inout.sub :word :spaces
repeat :spaces [type "| |]
print :word
if equalp count :word 1 [stop]
inout.sub (butfirst :word) (:spaces+1)
repeat :spaces [type "| |]
print :word
end
</PRE>
<P>
(The easiest way to make this change is to edit <CODE>inout</CODE>
with the Logo editor and change its title line and its recursive call
so that its name is <CODE>inout.sub</CODE>. Then, still in the editor,
type in the new superprocedure <CODE>inout</CODE>. When you leave the
editor, both procedures will get their new definitions.)
<P>
This program structure, with a short superprocedure and a recursive
subprocedure, is very common. The superprocedure's only job is to provide
the initial values for some of the subprocedure's inputs, so it's sometimes
called an <EM>initialization procedure.</EM> In this program
<CODE>inout</CODE> is an initialization procedure for <CODE>inout.sub</CODE>.
<P>
By the way, the parentheses in the recursive call aren't really
needed; I just used them to make it more obvious which input is which.
<H2>Other Stop Rules</H2>
<P>
The examples I've shown so far use this stop rule:
<PRE>
if equalp count :word 1 [stop]
</PRE>
<P>
Perhaps you wrote your <CODE>down</CODE> procedure the same way:
<PRE>
to down :word
print :word
if equalp count :word 1 [stop]
down butlast :word
end
</PRE>
<P>
Here is another way to write <CODE>down</CODE>, which has the same
effect. But this is a more commonly used style:
<PRE>
to down :word
if emptyp :word [stop]
print :word
down butlast :word
end
</PRE>
<P>
This version of <CODE>down</CODE> has the stop rule as its first
instruction. After that comes the instructions that carry out the
specific work of the procedure, in this case the <CODE>print</CODE>
instruction. The recursive call comes as the last instruction.
<P>
A procedure in which the recursive call is the last instruction is
called <EM>tail recursive.</EM> We'll have more to say later about the
meaning of tail recursion. (Actually, to be precise, I should have
said that a <EM>command</EM> in which the recursive call is the last
instruction is tail recursive. What constitutes a tail recursive
operation is a little tricker, and so far we haven't talked about
recursive operations at all.)
<P>
Here's another example:
<PRE>
to countdown :number
if equalp :number 0 [print "Blastoff! stop]
print :number
countdown :number-1
end
? <U>countdown 10</U>
10
9
8
7
6
5
4
3
2
1
Blastoff!
</PRE>
<P>
In this case, instead of a word that gets smaller by
<CODE>butfirst</CODE>ing or <CODE>butlast</CODE>ing it, the input is a
number from which 1 is subtracted for each recursive invocation. This
example also shows how some special action (the <CODE>print
"Blastoff!</CODE> instruction) can be taken in the innermost invocation of
the procedure.
<P>
» Here are some ideas for recursive programs you can write. In each
case I'll show an example or two of what the program should do.
Start with <CODE>one.per.line</CODE>, a command with one input. If the input
is a word, the procedure should print each letter of the word on a
separate line. If the input is a list, the procedure should print
each member of the list on a separate line:
<PRE>
? <U>one.per.line "hello</U>
h
e
l
l
o
? <U>one.per.line [the rain in spain]</U>
the
rain
in
spain
</PRE>
<P>
(You already know how to do this without recursion, using
<CODE>foreach</CODE> instead. Many, although not all, recursive problems
can also be solved using higher order functions. You might enjoy this
non-obvious example:
<PRE>
to down :word
ignore cascade (count :word) [print ? butlast ?] :word
end
</PRE>
<P>
While you're learning about recursion, though, don't use higher
order functions. Once you're comfortable with both techniques you can
choose which to use in a particular situation.)
<P>
» As an example in which an initialization procedure will be helpful,
try <CODE>triangle</CODE>, a command that takes a word as its single input.
It prints the word repeatedly on the same line, as many times as its
length. Then it prints a second line with one fewer repetition, and
so on until it prints the word just once:
<PRE>
? <U>triangle "frog</U>
frog frog frog frog
frog frog frog
frog frog
frog
</PRE>
<P>
» A more ambitious project is <CODE>diamond</CODE>, which takes as its input a
word with an odd number of letters. It displays the word in a diamond
pattern, like this:
<PRE>
? <U>diamond "program</U>
g
ogr
rogra
program
rogra
ogr
g
</PRE>
<P>
(Hint: Write two procedures <CODE>diamond.top</CODE> and
<CODE>diamond.bottom</CODE> for the growing and shrinking halves of the display.
As in <CODE>inout</CODE>, you'll need an input to count the number of spaces
by which to indent each line.) Can you write <CODE>diamond</CODE> so that it
does something sensible for an input word with an even number of
letters?
<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A>
<P><A HREF="../v1ch6/v1ch6.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v1ch8/v1ch8.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|