# SICP 1.2 exercises

**Posted:**January 4, 2013

**Filed under:**Improving, SICP Leave a comment

**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.*

(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?*

First analyze the first one:

(define (+ a b) (if (= a 0) b (inc (+ (dec a) b))))

(+ 4 5) expands as follows:

(+ 4 5) (inc (+ 3 5)) (inc (inc (+ 2 5))) (inc (inc (inc (+ 1 5)))) (inc (inc (inc (inc (+ 0 5))))) (inc (inc (inc (inc 5)))) (inc (inc (inc 6))) (inc (inc 7)) (inc 8) 9

It is characterized by expansion followed by contraction so it is a recursive process.

Using the second procedure:

(define (+ a b) (if (= a 0) b (+ (dec a) (inc b))))

(+ 4 5) expands as follows:

(+ 4 5) (+ 3 6) (+ 2 7) (+ 1 8) (+ 0 9) 9

The process does not grow and shrink, so it is iterative.

**Comments:** Thanks to the previous section, this was straightforward for me. I thought about writing out the substitutions first and then evaluating, but I figured that’s not the important part of this exercise.

**1.10 **

The following procedure computes a mathematical function called Ackermann’s function.

(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?

*(A 1 10)*

I’m not intelligent enough to do this in my head so I’ll write it out.

(A 1 10) (A 0 (A 1 9)) (A 0 (A 0 (A 1 8))) (A 0 (A 0 (A 0 (A 1 7)))) (A 0 (A 0 (A 0 (A 0 (A 1 6))))) ... (A 0 (A 0 (... (A 0 (A 1 1)) ... ) (A 0 (A 0 (... (A 0 2)))... ) (A 0 (A 0 (... 4 ) ...) ... 1024 (A 2 4) (A 1 (A 2 3)) (A 1 (A 1 (A 2 2))) (A 1 (A 1 (A 1 (A 2 1)))) (A 1 (A 1 (A 1 2))) (A 1 (A 1 (A 0 (A 1 1)))) (A 1 (A 1 (A 0 2))) (A 1 (A 1 4)) (A 1 (A 0 (A 1 3))) (A 1 (A 0 (A 0 (A 1 2)))) (A 1 (A 0 (A 0 (A 0 (A 1 1))))) (A 1 (A 0 (A 0 (A 0 2)))) (A 1 (A 0 (A 0 4))) (A 1 (A 0 8)) (A 1 16) #not going to do the full expansion here, same as above 65536 (A 3 3) (A 2 (A 3 2)) (A 2 (A 2 (A 3 1))) (A 2 (A 2 2)) (A 2 (A 1 (A 2 1))) (A 2 (A 1 2)) (A 2 (A 0 (A 1 1))) (A 2 (A 0 2)) (A 2 4) # which is the above term so do that and we get: 65536

Consider the following procedures, where A is the procedure defined above:

(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 5n^2.*

(f n) computes 2n

(g n) computes 2^n

(h n) computes 2^2^…^2 with n 2’s. Not sure if there’s a better way to write it.

**Comments:** Good practice for using the substitution method and observing the shape of the process.

Was pretty distracted today. Didn’t get a whole lot done. I started on the next question but won’t finish by my self imposed deadline.