SICP Section 1.2 Procedures and the Processes They Generate

Exercise 1.9. 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.

view plainprint?

1. (define (+ a b)  
2.   (if (= a 0)  
3.       b  
4.       (inc (+ (dec a) b))))  
5.   
6. (define (+ a b)  
7.   (if (= a 0)  
8.       b  
9.       (+ (dec a) (inc b))))  

(define (+ a b) (if (= a 0) b (inc (+ (dec a) b)))) (define (+ a b) (if (= a 0) b (+ (dec a) (inc b))))
Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?

Answer: First version is recursive; second is iterative. Exercise 1.10. The following procedure computes a mathematical function called Ackermann's function.

view plainprint?

1. (define (A x y)  
2.   (cond ((= y 0) 0)  
3.         ((= x 0) (* 2 y))  
4.         ((= y 1) 2)  
5.         (else (A (- x 1)  
6.                  (A x (- y 1))))))  

(define (A x y) (cond ((= y 0) 0) ((= x 0) (* 2 y)) ((= y 1) 2) (else (A (- x 1) (A x (- y 1))))))
What are the values of the following expressions?

1. (A 1 10)  
2.   
3. (A 2 4)  
4.   
5. (A 3 3)  

(A 1 10) (A 2 4) (A 3 3)
Consider the following procedures, where A is the procedure defined above:

view plainprint?

1. (define (f n) (A 0 n))  
2.   
3. (define (g n) (A 1 n))  
4.   
5. (define (h n) (A 2 n))  
6.   
7. (define (k n) (* 5 n n))  

(define (f n) (A 0 n)) (define (g n) (A 1 n)) (define (h n) (A 2 n)) (define (k n) (* 5 n n))
Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes 5n2.

Answer:

view plainprint?

1. (A 1 10) ;; 2^10 = 1024  
2. (A 2 4) ;; 65536  
3. (A 3 3) ;; 65536  
4.   
5. (define (f n) (A 0 n)) ;; (f n) computes 2n  
6. (define (g n) (A 1 n)) ;; (g n) computes 2^n  
7. (define (h n) (A 2 n)) ;; (h n) computes 0 if n = 0; 2 if n = 1; 2^h(n-1) for n > 1  

(A 1 10) ;; 2^10 = 1024 (A 2 4) ;; 65536 (A 3 3) ;; 65536 (define (f n) (A 0 n)) ;; (f n) computes 2n (define (g n) (A 1 n)) ;; (g n) computes 2^n (define (h n) (A 2 n)) ;; (h n) computes 0 if n = 0; 2 if n = 1; 2^h(n-1) for n > 1
Exercise 1.11. 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. Write a procedure that computes f by means of an iterative process.

view plainprint?

1. ;; Recursive version  
2. (define (f n)  
3.   (cond ((< n 3) n)  
4.         (else (+  
5.                (f (- n 1))  
6.                (* 2 (f (- n 2)))  
7.                (* 3 (f (- n 3)))))))  
8.   
9. ;; Iterative version  
10. (define (g n)  
11.   (cond ((< n 3) n)  
12.         (else (g-iter 2 1 0 (- n 2)))))  
13.   
14. (define (g-iter a b c count)  
15.   (if (= count 1)  
16.       (g-sum a b c)  
17.       (g-iter (g-sum a b c) a b (- count 1))))  
18.   
19. (define (g-sum a b c)  
20.   (+ a (* 2 b) (* 3 c)))  

;; Recursive version (define (f n) (cond ((< n 3) n) (else (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))) ;; Iterative version (define (g n) (cond ((< n 3) n) (else (g-iter 2 1 0 (- n 2))))) (define (g-iter a b c count) (if (= count 1) (g-sum a b c) (g-iter (g-sum a b c) a b (- count 1)))) (define (g-sum a b c) (+ a (* 2 b) (* 3 c)))
Exercise 1.12. The following pattern of numbers is called Pascal's triangle. 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.35 Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

Answer:

view plainprint?

1. (define (pascal row column)  
2.   (cond ((= row 1) 1)  
3.         ((= column 1) 1)  
4.         ((= row column) 1)  
5.         (else (+   
6.                (pascal (- row 1) (- column 1))  
7.                (pascal (- row 1) column)))))  

(define (pascal row column) (cond ((= row 1) 1) ((= column 1) 1) ((= row column) 1) (else (+ (pascal (- row 1) (- column 1)) (pascal (- row 1) column)))))
Exercise 1.14. 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?

Answer: Amount (steps and space) are respectively 1 (10), 2 (12), 3 (14) etc. Therefore space and # of steps grows linearly with amount. O(n).