forked from ldct/isicp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
1-2-procedures.html
1448 lines (1086 loc) · 79.5 KB
/
1-2-procedures.html
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
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html>
<head>
<meta charset="UTF-8">
<link rel="stylesheet" type="text/css" href="web-worker-interpreter/deps/codemirror/lib/codemirror.css" />
<link rel="stylesheet" type="text/css" href="css/isicp.css" />
<link rel="stylesheet" type="text/css" href="css/footnotes.css" />
<link rel="stylesheet" type="text/css" href="css/theme.css" />
<script src="js/helper.js"></script>
<script src="js/jquery.min.js"></script>
<script src="web-worker-interpreter/deps/codemirror/lib/codemirror.js"></script>
<script src="web-worker-interpreter/deps/codemirror/mode/scheme/scheme.js"></script>
<script src="web-worker-interpreter/coding.js"> </script>
<script>
set_interpreter_path("web-worker-interpreter/");
set_language("scheme");
</script>
<script src="js/footnotes.js"></script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$']]}
});
</script>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<title> iSICP 1.2 - Procedures and the Processes They Generate </title>
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-36868476-1']);
_gaq.push(['_trackPageview']);
(function() {
var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>
</head>
<body>
<div id="sidebox">
<div class="tab"></div>
<div class="content">
<p>
<a href="index.html" class="navlink"> <img src='images/home.svg' width=32 height=32> </a>
<span id="toc-link" class="navlink"> <img src='images/list.svg' width=32 height=32> </span>
<span id="currently-editing-link" class="navlink"> <img src='images/file-edit.svg' width=32 height=32> </span>
<script src="http://cdn.jotfor.ms/static/feedback2.js?3.2.310" type="text/javascript">
new JotformFeedback({
formId:'40222623177447',
base:'http://jotform.me/',
windowTitle:'Notify Me',
background:'#FFA500',
fontColor:'#FFFFFF',
type:false,
height:500,
width:700
});
</script>
<a class="lightbox-40222623177447" style="cursor:pointer;color:blue;text-decoration:underline;"><img src='images/envelope.svg' width=32 height=32></a>
<p>
<div id="currently-editing"> </div>
<script>
function hideAll() {
$("#currently-editing").hide();
$("#toc").hide();
}
$("#currently-editing-link").click(function() {
hideAll();
$("#currently-editing").show();
});
$("#toc-link").click(function() {
hideAll();
$("#toc").show();
});
</script>
<div id="toc"> </div>
<p style='font-size:12px'> (Click on the left edge of this green box to hide it!)
<script>
hideAll();
$("#toc").show();
</script>
</div>
</div>
<script>
$('#sidebox .tab').toggle(function(){
$('#sidebox').animate({'right':'0%'});
}, function(){
$('#sidebox').animate({'right':'-30%'});
});
$(document).ready(createTOC);
</script>
<div id="main">
<a href='index.html' style="float:left"> <img src='images/chevron-up.svg' height=64 width=64> </a>
<span style="float:right">
<a href='1-1-elements.html'> <img src='images/chevron-left.svg' height=64 width=64> </a>
<a href='1-3-hop.html'> <img src='images/chevron-right.svg' height=64 width=64> </a>
</span>
<br> <br>
<h2> Procedures and the Processes They Generate </h2>
<hr>
<p> We have now considered the elements of programming: We have used primitive arithmetic operations, we have combined these operations, and we have abstracted these composite operations by defining them as compound procedures. But that is not enough to enable us to say that we know how to program. Our situation is analogous to that of someone who has learned the rules for how the pieces move in chess but knows nothing of typical openings, tactics, or strategy. Like the novice chess player, we don't yet know the common patterns of usage in the domain. We lack the knowledge of which moves are worth making (which procedures are worth defining). We lack the experience to predict the consequences of making a move (executing a procedure).
<p> The ability to visualize the consequences of the actions under consideration is crucial to becoming an expert programmer, just as it is in any synthetic, creative activity. In becoming an expert photographer, for example, one must learn how to look at a scene and know how dark each region will appear on a print for each possible choice of exposure and development conditions. Only then can one reason backward, planning framing, lighting, exposure, and development to obtain the desired effects. So it is with programming, where we are planning the course of action to be taken by a process and where we control the process by means of a program. To become experts, we must learn to visualize the processes generated by various types of procedures. Only after we have developed such a skill can we learn to reliably construct programs that exhibit the desired behavior.
<p> A procedure is a pattern for the local evolution of a computational process. It specifies how each stage of the process is built upon the previous stage. We would like to be able to make statements about the overall, or global, behavior of a process whose local evolution has been specified by a procedure. This is very difficult to do in general, but we can at least try to describe some typical patterns of process evolution.
<p> In this section we will examine some common “shapes” for processes generated by simple procedures. We will also investigate the rates at which these processes consume the important computational resources of time and space. The procedures we will consider are very simple. Their role is like that played by test patterns in photography: as oversimplified prototypical patterns, rather than practical examples in their own right.
<h3> Linear Recursion and Iteration </h3>
<p> We begin by considering the factorial function, defined by
$$
n! = n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1 \\
$$
There are many ways to compute factorials. One way is to make use of the observation that n! is equal to n times (n - 1)! for any positive integer n:
\begin{align}
n! &= n \cdot [(n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1] \\
&= n \cdot (n-1)!
\end{align}
<p> Thus, we can compute $n!$ by computing $(n - 1)!$ and multiplying the result by $n$. If we add the stipulation that $1!$ is equal to $1$, this observation translates directly into a procedure:
<div id="scheme-define-factorial">
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
</div>
<script>
prompt("scheme-define-factorial");
</script>
<p> We can use the substitution model of section 1.1.5 to watch this procedure in action computing 6!, as shown in figure 1.3.
<p> <img class="center" src="http://mitpress.mit.edu/sicp/full-text/book/ch1-Z-G-7.gif"> </img> <br>
<p style="text-align:center"> <b> Figure 1.3: </b> A linear recursive process for computing 6!.
<p> Now let's take a different perspective on computing factorials. We could describe a rule for computing n! by specifying that we first multiply 1 by 2, then multiply the result by 3, then by 4, and so on until we reach n. More formally, we maintain a running product, together with a counter that counts from 1 up to n. We can describe the computation by saying that the counter and the product simultaneously change from one step to the next according to the rule
$$
\def\product{\text{product}}
\def\counter{\text{counter}}
\begin{align}
\product &\leftarrow \counter \cdot \product \\
\counter &\leftarrow \counter + 1
\end{align}
$$
<p> and stipulating that n! is the value of the product when the counter exceeds n.
<p> Once again, we can recast our description as a procedure for computing factorials:<a name="footnote_link_1-29" class="footnote_link" href="#footnote_1-29">29</a>
<div id="scheme-define-factorial-iterative">
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
</div>
<script>
prompt("scheme-define-factorial-iterative");
</script>
<p> As before, we can use the substitution model to visualize the process of computing 6!, as shown in figure 1.4.
<p> <img class="center" src="http://mitpress.mit.edu/sicp/full-text/book/ch1-Z-G-10.gif"> </img> <br>
<p style="text-align:center"> <b> Figure 1.4: </b> A linear iterative process for computing 6!.
<p> Compare the two processes. From one point of view, they seem hardly different at all. Both compute the same mathematical function on the same domain, and each requires a number of steps proportional to n to compute n!. Indeed, both processes even carry out the same sequence of multiplications, obtaining the same sequence of partial products. On the other hand, when we consider the “shapes” of the two processes, we find that they evolve quite differently.
<p> Consider the first process. The substitution model reveals a shape of expansion followed by contraction, indicated by the arrow in figure 1.3. The expansion occurs as the process builds up a chain of deferred operations (in this case, a chain of multiplications). The contraction occurs as the operations are actually performed. This type of process, characterized by a chain of deferred operations, is called a recursive process. Carrying out this process requires that the interpreter keep track of the operations to be performed later on. In the computation of n!, the length of the chain of deferred multiplications, and hence the amount of information needed to keep track of it, grows linearly with n (is proportional to n), just like the number of steps. Such a process is called a linear recursive process.
<p> By contrast, the second process does not grow and shrink. At each step, all we need to keep track of, for any n, are the current values of the variables product, counter, and max-count. We call this an iterative process. In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate. In computing n!, the number of steps required grows linearly with n. Such a process is called a linear iterative process.
<p> The contrast between the two processes can be seen in another way. In the iterative case, the program variables provide a complete description of the state of the process at any point. If we stopped the computation between steps, all we would need to do to resume the computation is to supply the interpreter with the values of the three program variables. Not so with the recursive process. In this case there is some additional “hidden” information, maintained by the interpreter and not contained in the program variables, which indicates “where the process is” in negotiating the chain of deferred operations. The longer the chain, the more information must be maintained.<a name="footnote_link_1-30" class="footnote_link" href="#footnote_1-30">30</a>
<p> In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.
<p> One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.<a name="footnote_link_1-31" class="footnote_link" href="#footnote_1-31">31</a>
<div class="exercise">
<p> <b> Exercise 1.9. </b> Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.
<div id="scheme-define-plus">
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
</div>
<p>
<div id="scheme-define-plus-dec-inc">
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
</div>
<div id="scheme-define-inc-dec">
(define old-plus +)
(define old-minus -)
(define (inc n)
(old-plus n 1))
(define (dec n)
(old-minus n 1))
</div>
<script>
prompt("scheme-define-plus");
prompt("scheme-define-plus-dec-inc");
hidden_prompt("scheme-define-inc-dec");
addDep("scheme-define-plus", ["scheme-define-inc-dec"]);
addDep("scheme-define-plus-dec-inc", ["scheme-define-inc-dec"]);
</script>
<p> Using the substitution model, illustrate the process generated by each procedure in evaluating <tt>(+ 4 5).</tt> Are these processes iterative or recursive?
<div id="scheme-ex-dec-inc-mcq"></div>
<script>
makeMCQ("scheme-ex-dec-inc-mcq",
["The first procedure is recursive",
"The second procedure is iterative"],
["The first procedure is iterative",
"The second procedure is recursive"
]);
</script>
</div>
<p>
<div class="exercise">
<p> <b> Exercise 1.10. </b> The following procedure computes a mathematical function called Ackermann's function.
<div id="scheme-define-ackerman">
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
</div>
<script>
makeStatic("scheme-define-ackerman");
</script>
<p> What are the values of the following expressions?
<div id="scheme-a-1-10">
(A 1 10)
</div>
<div id="scheme-a-2-4">
(A 2 4)
</div>
<div id="scheme-a-3-3">
(A 3 3)
</div>
<script>
answer("scheme-a-1-10", 1024);
answer("scheme-a-2-4" , 65536);
answer("scheme-a-3-3" , 65536);
</script>
<p> Consider the following procedures, where <tt>A</tt> is the procedure defined above:
<div id="scheme-define-a-0-n">
(define (f n) (A 0 n))
</div>
<div id="scheme-define-a-1-n">
(define (g n) (A 1 n))
</div>
<div id="scheme-define-a-2-n">
(define (h n) (A 2 n))
</div>
<div id="scheme-define-5-n-squared">
(define (k n) (* 5 n n))
</div>
<script>
makeStatic("scheme-define-a-0-n");
makeStatic("scheme-define-a-1-n");
makeStatic("scheme-define-a-2-n");
makeStatic("scheme-define-5-n-squared");
</script>
<p> Give concise mathematical definitions for the functions computed by the procedures $f$, $g$, and $h$ for positive integer values of $n$. For example, <tt>(k n)</tt> computes $5n^2$.
</div>
<h3> Tree Recursion </h3>
<p> Another common pattern of computation is called tree recursion. As an example, consider computing the sequence of Fibonacci numbers, in which each number is the sum of the preceding two:
$$
0,1,1,2,3,5,8,13
$$
<p> In general, the Fibonacci numbers can be defined by the rule
$$
\def\Fib{\text{Fib}}
\Fib(n) = \begin{cases}
0 &\mbox{if } n = 0 \\
1 &\mbox{if } n = 1 \\
\Fib(n-1) + \Fib(n-2) &\mbox{otherwise}
\end{cases}
$$
<p> We can immediately translate this definition into a recursive procedure for computing Fibonacci numbers:
<div id="scheme-define-fib">
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
</div>
<script>
prompt("scheme-define-fib");
</script>
<br>
<p> <img class="center" src='http://mitpress.mit.edu/sicp/full-text/book/ch1-Z-G-13.gif'>
<p style="text-align:center"> <b> Figure 1.5: </b> The tree-recursive process generated in computing (fib 5).
<p> Consider the pattern of this computation. To compute (fib 5), we compute (fib 4) and (fib 3). To compute (fib 4), we compute (fib 3) and (fib 2). In general, the evolved process looks like a tree, as shown in figure 1.5. Notice that the branches split into two at each level (except at the bottom); this reflects the fact that the fib procedure calls itself twice each time it is invoked.
<p> This procedure is instructive as a prototypical tree recursion, but it is a terrible way to compute Fibonacci numbers because it does so much redundant computation. Notice in figure 1.5 that the entire computation of (fib 3) — almost half the work — is duplicated. In fact, it is not hard to show that the number of times the procedure will compute (fib 1) or (fib 0) (the number of leaves in the above tree, in general) is precisely Fib(n + 1). To get an idea of how bad this is, one can show that the value of Fib(n) grows exponentially with n. More precisely (see exercise 1.13), Fib(n) is the closest integer to $\phi^n / 5$ where
$$
\phi = \frac{1 + \sqrt 5}{2} = 1.6180339887\ldots
$$
<p> is the golden ratio, which satisfies the equation
$$
\phi + 1 = \phi^2
$$
<p> Thus, the process uses a number of steps that grows exponentially with the input. On the other hand, the space required grows only linearly with the input, because we need keep track only of which nodes are above us in the tree at any point in the computation. In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.
<p> We can also formulate an iterative process for computing the Fibonacci numbers. The idea is to use a pair of integers $a$ and $b$, initialized to $\Fib(1) = 1$ and $\Fib(0) = 0$, and to repeatedly apply the simultaneous transformations
\begin{align}
a &\leftarrow a+b \\
b &\leftarrow b
\end{align}
<p> It is not hard to show that, after applying this transformation $n$ times, $a$ and $b$ will be equal, respectively, to $\Fib(n + 1)$ and $\Fib(n)$. Thus, we can compute Fibonacci numbers iteratively using the procedure
<div id="scheme-define-fib-iterative">
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
</div>
<script>
prompt("scheme-define-fib-iterative");
</script>
<p> This second method for computing Fib(n) is a linear iteration. The difference in number of steps required by the two methods — one linear in n, one growing as fast as Fib(n) itself — is enormous, even for small inputs.
<p> One should not conclude from this that tree-recursive processes are useless. When we consider processes that operate on hierarchically structured data rather than numbers, we will find that tree recursion is a natural and powerful tool.<a name="footnote_link_1-32" class="footnote_link" href="#footnote_1-32">32</a> But even in numerical operations, tree-recursive processes can be useful in helping us to understand and design programs. For instance, although the first fib procedure is much less efficient than the second one, it is more straightforward, being little more than a translation into Lisp of the definition of the Fibonacci sequence. To formulate the iterative algorithm required noticing that the computation could be recast as an iteration with three state variables.
<h4>Example: Counting change</h4>
<p> It takes only a bit of cleverness to come up with the iterative Fibonacci algorithm. In contrast, consider the following problem: How many different ways can we make change of $ 1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?
<p> This problem has a simple solution as a recursive procedure. Suppose we think of the types of coins available as arranged in some order. Then the following relation holds:
<p> The number of ways to change amount a using n kinds of coins equals
<ul>
<li> <p> the number of ways to change amount a using all but the first kind of coin, plus </li>
<li> <p> the number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin. </li>
</ul>
<p> To see why this is true, observe that the ways to make change can be divided into two groups: those that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin. But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind.
<p> Thus, we can recursively reduce the problem of changing a given amount to the problem of changing smaller amounts using fewer kinds of coins. Consider this reduction rule carefully, and convince yourself that we can use it to describe an algorithm if we specify the following degenerate cases:<a name="footnote_link_1-33" class="footnote_link" href="#footnote_1-33">33</a>
<ul>
<li> <p> If a is exactly 0, we should count that as 1 way to make change. </li>
<li> <p> If a is less than 0, we should count that as 0 ways to make change. </li>
<li> <p> If n is 0, we should count that as 0 ways to make change. </li>
</ul>
<p> We can easily translate this description into a recursive procedure:
<div id="scheme-define-count-change">
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
</div>
<script>
prompt("scheme-define-count-change");
</script>
<p> The first-denomination procedure takes as input the number of kinds of coins available and returns the denomination of the first kind. Here we are thinking of the coins as arranged in order from largest to smallest, but any order would do as well.) We can now answer our original question about changing a dollar:
<div id="scheme-count-change-100">
(count-change 100)
</div>
<script>
prompt("scheme-count-change-100");
addDep("scheme-count-change-100", ["scheme-define-count-change"]);
</script>
<p> Count-change generates a tree-recursive process with redundancies similar to those in our first implementation of fib. (It will take quite a while for that 292 to be computed.) On the other hand, it is not obvious how to design a better algorithm for computing the result, and we leave this problem as a challenge. The observation that a tree-recursive process may be highly inefficient but often easy to specify and understand has led people to propose that one could get the best of both worlds by designing a “smart compiler” that could transform tree-recursive procedures into more efficient procedures that compute the same result.<a name="footnote_link_1-34" class="footnote_link" href="#footnote_1-34">34</a>
<div class="exercise">
<p> <b> Exercise 1.11. </b> A function $f$ is defined by the rule that $f(n) = n$ if $n<3$ and $f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)$ if $n > 3$. Write a procedure that computes $f$ by means of a recursive process.
<p> Write a procedure that computes f by means of an iterative process.
<div id="scheme-ex-fn-3-input" class='input'></div>
</div>
<script>
makeChangeOnFocusInput("scheme-ex-fn-3-input",
"(define (f n)\n 'your-code-here)",
"(define (f n)\n ");
addOutput("scheme-ex-fn-3-input");
editorOf["scheme-ex-fn-3-input"].setOption("onBlur", function() {
function f(n) {
if (n < 3) {
return n;
} else {
return f(n-1) + 2*f(n-2) + 3*f(n-3);
}
}
function fs(n) {
return "(= (f " + n + ") " + f(n) + ")";
}
var code = editorOf["scheme-ex-fn-3-input"].getValue() + "\n" +
"(and " + fs(1) +
fs(10) +
fs(3) + ")";
eval_scheme(code).then(function(res){
if (res[res.length - 1] === "true") {
$_("scheme-ex-fn-3-input-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
} else {
$_("scheme-ex-fn-3-input-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
}
})
});
</script>
<!--
(define (f n)
(if (< n 3)
n
(+ (* 1 (f (- n 1)))
(* 2 (f (- n 2)))
(* 3 (f (- n 3))))))
!-->
<p>
<div class="exercise">
<p> <b> Exercise 1.12. </b> The following pattern of numbers is called Pascal's triangle.
<p> <img style="display:block; margin-left:auto; margin-right:auto; width:30%" src='http://upload.wikimedia.org/wikipedia/commons/thumb/f/f6/Pascal%27s_triangle_5.svg/540px-Pascal%27s_triangle_5.svg.png'>
<p> The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.<a name="footnote_link_1-35" class="footnote_link" href="#footnote_1-35">35</a>
<p> Write a procedure that computes elements of Pascal's triangle by means of a recursive process. If a number lies outside of the triangle, return 0 (this makes sense if we view <tt>pascal</tt> as the <a href='http://en.wikipedia.org/wiki/Combination' target="_blank"> combination function </a>). Start counting rows and columns from 0.
<div id="scheme-ex-pascal-input" class='input'></div>
<script>
makeChangeOnFocusInput("scheme-ex-pascal-input",
"(define (pascal row col)\n 'your-code-here)",
"(define (pascal row col)\n ");
addOutput("scheme-ex-pascal-input");
editorOf["scheme-ex-pascal-input"].setOption("onBlur", function(){
function pascal(row, col) {
if (row < col) {
return 0;
} else if (col == 0 || row == col) {
return 1;
} else
return pascal(row - 1, col) +
pascal(row - 1, col - 1);
}
function ps(row, col) {
return "(= (pascal " + row + " " + col + ") " + pascal(row, col) + ") ";
}
var code = editorOf["scheme-ex-pascal-input"].getValue() + "\n" +
"(and " + ps(3,2) +
ps(2,1) +
ps(4,3) + ")"
eval_scheme(code).then(function(res){
console.log(res);
if (res[res.length - 1] === "true") {
$_("scheme-ex-pascal-input-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
} else {
$_("scheme-ex-pascal-input-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
}
})
});
</script>
<!--
(define (pascal row col)
(cond ((< row col) 0)
((or (= 0 col) (= row col)) 1)
(else (+ (pascal (- row 1) col)
(pascal (- row 1) (- col 1))))))
!-->
</div>
<p>
<div class="exercise">
<p> <b> Exercise 1.13. </b> Prove that $\Fib(n)$ is the closest integer to $\phi^n / 5$, where
$$
\phi = \frac{1 + \sqrt 5}{2} \approx 1.6180339887
$$
<p> Hint: Let
$$
\psi = \frac{1 - \sqrt 5}{2} = 1 - \phi = -\frac{1}{\phi} \approx -0.6180339887
$$
<p> Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that
$$
\Fib(n) = \frac{\phi^n - \psi^n}{\phi - \psi} = \frac{\phi^n - \psi^n}{\sqrt 5}
$$
</div>
<h3> Orders of Growth </h3>
<p> The previous examples illustrate that processes can differ considerably in the rates at which they consume computational resources. One convenient way to describe this difference is to use the notion of order of growth to obtain a gross measure of the resources required by a process as the inputs become larger.
<p> Let $n$ be a parameter that measures the size of the problem, and let $R(n)$ be the amount of resources the process requires for a problem of size $n$. In our previous examples we took n to be the number for which a given function is to be computed, but there are other possibilities. For instance, if our goal is to compute an approximation to the square root of a number, we might take n to be the number of digits accuracy required. For matrix multiplication we might take $n$ to be the number of rows in the matrices. In general there are a number of properties of the problem with respect to which it will be desirable to analyze a given process. Similarly, $R(n)$ might measure the number of internal storage registers used, the number of elementary machine operations performed, and so on. In computers that do only a fixed number of operations at a time, the time required will be proportional to the number of elementary machine operations performed.
<p> We say that $R(n)$ has order of growth $(f(n))$, written $R(n) = \Theta(f(n))$ (pronounced "theta of $f(n)$"), if there are positive constants $k_1$ and $k_2$ independent of $n$ such that
$$
k_1 f(n) \leq R(n) \leq k_2 f(n)
$$
<p> for any sufficiently large value of n. (In other words, for large n, the value R(n) is sandwiched between $k_1 f(n)$ and $k_2f(n)$.)
<p> For instance, with the linear recursive process for computing factorial described in section 1.2.1 the number of steps grows proportionally to the input $n$. Thus, the steps required for this process grows as $\Theta(n)$. We also saw that the space required grows as $\Theta(n)$. For the iterative factorial, the number of steps is still $\Theta(n)$ but the space is $\Theta(1)$ — that is, constant.<a name="footnote_link_1-36" class="footnote_link" href="#footnote_1-36">36</a> The tree-recursive Fibonacci computation requires $\Theta(\phi^n)$ steps and space $\Theta(n)$, where is the golden ratio described in section 1.2.2.
<p> Orders of growth provide only a crude description of the behavior of a process. For example, a process requiring n2 steps and a process requiring 1000n2 steps and a process requiring 3n2 + 10n + 17 steps all have (n2) order of growth. On the other hand, order of growth provides a useful indication of how we may expect the behavior of the process to change as we change the size of the problem. For a (n) (linear) process, doubling the size will roughly double the amount of resources used. For an exponential process, each increment in problem size will multiply the resource utilization by a constant factor. In the remainder of section 1.2 we will examine two algorithms whose order of growth is logarithmic, so that doubling the problem size increases the resource requirement by a constant amount.
<div class='exercise'>
<p> <b> Exercise 1.14. </b> Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?
</div>
<p>
<div class='exercise'>
<p> <b> Exercise 1.15. </b> The sine of an angle (specified in radians) can be computed by making use of the approximation $\sin(x) = x$ if $x$ is sufficiently small, and the trigonometric identity
$$
\sin(x) = 3 \sin(\frac{x}{3}) - 4\sin^3(\frac{x}{3})
$$
<p> to reduce the size of the argument of sin. (For purposes of this exercise an angle is considered “sufficiently small” if its magnitude is not greater than 0.1 radians.) These ideas are incorporated in the following procedures:
<div id="scheme-define-sine">
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
</div>
<script>
prompt("scheme-define-sine");
</script>
<ol style="list-style-type: lower-alpha">
<li> <p> How many times is the procedure p applied when (sine 12.15) is evaluated?
<div id="scheme-sine-1215-qns" style="display:none"></div>
<script>
answer("scheme-sine-1215-qns", 5);
</script>
</li>
<br>
<li> <p> What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?
<p>
<div id="scheme-sine-order-mcq"></div>
<script>
makeMCQ("scheme-sine-order-mcq",
["$\\Theta(\\log(n))$"],
["$\\Theta(n)$",
"$\\Theta(n^2)$",
"$\\Theta(\\sqrt{n})$",
"$\\Theta(n/3)$"
]);
</script>
</li>
</ol>
</div>
<h3> Exponentiation </h3>
<p> Consider the problem of computing the exponential of a given number. We would like a procedure that takes as arguments a base b and a positive integer exponent n and computes bn. One way to do this is via the recursive definition
\begin{align}
b^n &= b \cdot b^{n-1} \\
b^0 &= 1
\end{align}
<p> which translates readily into the procedure
<div id="scheme-define-expt">
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
</div>
<script>
prompt("scheme-define-expt");
</script>
<p> This is a linear recursive process, which requires Θ(n) steps and Θ(n) space. Just as with factorial, we can readily formulate an equivalent linear iteration:
<div id="scheme-define-expt-iterative">
(define (expt b n)
(expt-iter b n 1))
(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b
(- counter 1)
(* b product))))
</div>
<script>
prompt("scheme-define-expt-iterative");
</script>
<p> This version requires $\Theta(n)$ steps and $\Theta(1)$ space.
<p> We can compute exponentials in fewer steps by using successive squaring. For instance, rather than computing $b^8$ as
$$
b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot b))))))
$$
<p> we can compute it using three multiplications:
\begin{align}
b^2 &= b \cdot b \\
b^4 &=b^2 \cdot b^2 \\
b^8 &=b^4 \cdot b^4
\end{align}
<p> This method works fine for exponents that are powers of 2. We can also take advantage of successive squaring in computing exponentials in general if we use the rule
\begin{align}
b^n = \begin{cases}
(b^{n/2})^2 &\mbox{if } n \text{ is even} \\
b \cdot b^{n-1} & \mbox{if } n \text{ is odd}. \end{cases}
\end{align}
<p> We can express this method as a procedure:
<div id="scheme-define-square">
(define (square x)
(* x x))
</div>
<script>
hidden_prompt("scheme-define-square");
</script>
<div id="scheme-define-fast-expt">
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
</div>
<script>
prompt("scheme-define-fast-expt");
addDep("scheme-define-fast-expt", ["scheme-define-even", "scheme-define-square"]);
</script>
<p> where the predicate to test whether an integer is even is defined in terms of the primitive procedure remainder by
<div id="scheme-define-even">
(define (even? n)
(= (remainder n 2) 0))
</div>
<script>
prompt("scheme-define-even");
</script>
<p> The process evolved by fast-expt grows logarithmically with n in both space and number of steps. To see this, observe that computing b2n using fast-expt requires only one more multiplication than computing bn. The size of the exponent we can compute therefore doubles (approximately) with every new multiplication we are allowed. Thus, the number of multiplications required for an exponent of n grows about as fast as the logarithm of n to the base 2. The process has (log n) growth.<a name="footnote_link_1-37" class="footnote_link" href="#footnote_1-37">37</a>
<p> The difference between Θ(log n) growth and Θ(n) growth becomes striking as n becomes large. For example, fast-expt for n = 1000 requires only 14 multiplications.<a name="footnote_link_1-38" class="footnote_link" href="#footnote_1-38">38</a> It is also possible to use the idea of successive squaring to devise an iterative algorithm that computes exponentials with a logarithmic number of steps (see exercise 1.16), although, as is often the case with iterative algorithms, this is not written down so straightforwardly as the recursive algorithm.<a name="footnote_link_1-39" class="footnote_link" href="#footnote_1-39">39</a>
<div class='exercise'>
<p> <b> Exercise 1.16. </b> Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that (b<sup>n/2</sup>)<sup>2</sup> = (b<sup>2</sup>)<sup>n/2</sup>, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product a bn is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an <em> invariant quantity </em> that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)
<div id="scheme-ex-fast-expt-iter-input">
(define (fast-expt b n)
'your-code-here)
</div>
<script>
makeEditable("scheme-ex-fast-expt-iter-input");
addOutput("scheme-ex-fast-expt-iter-input");
editorOf["scheme-ex-fast-expt-iter-input"].setOption("onBlur", function(){
function es(b, n) {
return "(= (fast-expt " + b + " " + n + ") " + Math.pow(b,n) + ") ";
}
var code = editorOf["scheme-ex-fast-expt-iter-input"].getValue() + "\n" +
"(and " + es(7,5) +
es(4,9) +
es(3,4) + ")"
eval_scheme(code).then(function(res){
console.log(res);
if (res[res.length - 1] == "true") {
$_("scheme-ex-fast-expt-iter-input-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
} else {
$_("scheme-ex-fast-expt-iter-input-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
}
})
});
</script>
</div>
<!--
(define (even? n)
(= (modulo n 2) 0))
(define (square x)
(* x x))
(define (expt-iter b n a)
(cond ((= n 0) a)
((even? n) (expt-iter (square b) (/ n 2) a))
(else (expt-iter b (- n 1) (* a b)))))
(define (fast-expt b n)
(expt-iter b n 1))
!-->
<p>
<div class='exercise'>
<p> <b> Exercise 1.17. </b> The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:
<div id="scheme-define-times">
(define (* a b)
(if (= b 0)
0
(+ a (* a (- b 1)))))
</div>
<script>
prompt("scheme-define-times");
</script>
<p> This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.
<div id="scheme-ex-mul-input">
(define (mul a b)
'your-code-here)
</div>
<script>
//TODO: halve, double
makeEditable("scheme-ex-mul-input");
addOutput("scheme-ex-mul-input");
editorOf["scheme-ex-mul-input"].setOption("onBlur", function(){
function ms(a, b) {
return "(= (mul " + a + " " + b + ") " + a*b + ") ";
}
var code = editorOf["scheme-ex-mul-input"].getValue() + "\n" +
"(and " + ms(7,5) +
ms(4,9) +
ms(3,4) + ")"
eval_scheme(code).then(function(res){
if (res[res.length - 1] == "true") {
$_("scheme-ex-mul-input-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
} else {
$_("scheme-ex-mul-input-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
}
});
});
</script>
</div>
<p>
<div class='exercise'>
<p> <b> Exercise 1.18. </b> Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.<a name="footnote_link_1-40" class="footnote_link" href="#footnote_1-40">40</a>
<div id="scheme-ex-mul-iter-input">
(define (mul a b)
'your-code-here)
</div>
<script>
makeEditable("scheme-ex-mul-iter-input")
addOutput("scheme-ex-mul-iter-input");
editorOf["scheme-ex-mul-iter-input"].setOption("onBlur", function() {
function ms(a, b) {
return "(= (mul " + a + " " + b + ") " + a*b + ")";
}
var code = editorOf["scheme-ex-mul-iter-input"].getValue() + "\n" +
"(and " + ms(7,5) +
ms(4,9) +
ms(3,4) + ") "
eval_scheme(code).then(function(res){
if (res[res.length - 1] == "true") {
$_("scheme-ex-mul-iter-input-output").empty().append($("<div class='right-answer'> \u2713 </div>"));
} else {
$_("scheme-ex-mul-iter-input-output").empty().append($("<div class='wrong-answer'> \u2717 </div>"));
}
});
});
</script>
</div>
<p>
<div class='exercise'>
<p> <b> Exercise 1.19. </b> There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables a and b in the fib-iter process of section 1.2.2:
\begin{align}
a &\leftarrow a + b \\
b &\leftarrow a
\end{align}
<p> Call this transformation T, and observe that applying T over and over again n times, starting with 1 and 0, produces the pair Fib(n + 1) and Fib(n). In other words, the Fibonacci numbers are produced by applying T<sup>n</sup>, the nth power of the transformation T, starting with the pair (1,0). Now consider T to be the special case of p = 0 and q = 1 in a family of transformations $T_{pq}$, where $T_{pq}$ transforms the pair $(a,b)$ according to
\begin{align}
a &\leftarrow bq + aq + ap \\
b &\leftarrow bp + aq
\end{align}
<p> Show that if we apply such a transformation $T_{pq}$ twice, the effect is the same as using a single transformation $T_{p'q'}$ of the same form, and compute $p'$ and $q'$ in terms of $p$ and $q$. This gives us an explicit way to square these transformations, and thus we can compute $T^n$ using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:<a name="footnote_link_1-41" class="footnote_link" href="#footnote_1-41">41</a>
<div id="scheme-ex-log-fib-input">
(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
<??> ; compute p'
<??> ; compute q'
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
</div>
<script>
makeEditable("scheme-ex-log-fib-input");
addOutput("scheme-ex-log-fib-input");
editorOf["scheme-ex-log-fib-input"].setOption("onBlur", function(){
function fib(n){
var i;
var fibs = [];
fibs.push(0);
fibs.push(1);
for(i=0; i<n; i++){
fibs.push(fibs[0] + fibs[1]);
fibs.shift();
}
return fibs[0];
}
function fibs(n) {
return "(= (fib " + n + ") " + fib(n) + ")";
}
var code = editorOf["scheme-ex-log-fib-input"].getValue() + "\n" +
"(and " + fibs(10) +
fibs(11) +
fibs(13) + ")"
eval_scheme(code).then(function(res){
if (res[res.length - 1] == "true") {
$_("scheme-ex-log-fib-input-output").empty().append($("<div class='right-answer'> \u2713 </div>"));