SICP Exercises 1.9 and 1.10

Exercises from section 1.21 Linear Recursion and Iteration

Exercise 1.9 asks us to use the substitution model to illustrate the processes generated by the following two procedures:

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

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

You may recognize these procedures as the two Peano Arithmetic examples from Lecture 1B. As we saw in the lecture video, the first procedure produces a linear recursive process, while the second produces an iterative process (the two procedures are given here in the reverse order from the lecture).

Remember also from that lecture that the steps for evaluating an application are:

• Evaluate the operator to get procedure
• Evaluate the operands to get arguments
• Apply the procedure to the arguments
• Copy the body of the procedure substituting the arguments supplied for the formal parameters of the procedure.
• Evaluate the resulting new body.

If we are to evaluate (+ 4 5) using the first procedure we'll see that the increment operations are deferred.

(+ 4 5)

Evaluate the operator to get the procedure

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

Evaluate the operands to get arguments

(if (= 4 0)
    5
    (inc (+ (dec 4) 5)))

Since 4 is in fact not equal to 0, this expression evaluates to

(inc (+ (dec 4) 5))

This is where things begin to get interesting. We can evaluate (dec 4), but then we need to evaluate the recursive call to + before we're able to evaluate the inc operation. That means the inc operation is deferred until we return from the recursive call.

Greatly simplified, the expansion of this expression proceeds as follows:

(inc (+ 3 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))

At this point, the innermost expression, (+ 0 5), can be evaluated because the first operand is 0, which is a the base case of the recursive definition. The process will now contract until we have our answer.

(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

Evaluating (+ 4 5) with the iterative procedure is much more straight forward, as we should expect. No operations are deferred, so we don't see the expand-and-contract process shape that is the signature of a recursive process.

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

Exercise 1.10 gives the following definition for Ackermann's function (note that this is a different definition than the one given in the Wikipedia entry for the Ackermann function. The analysis that follows is for the procedure given in the text.):

(define (A x y)
   (cond ((= y 0) 0)
         ((= x 0) (* 2 y))
         ((= y 1) 2)
         (else (A (- x 1)
                  (A x (- y 1))))))

The next part of the exercise asks us to evaluate a few expressions that use the function. Our Scheme interpreter is the best tool for this job.

> (A 1 10)
1024
> (A 2 4)
65536
> (A 3 3)
65536

Next, we're asked to give concise mathematical definitions for the following functions defined in terms of A:

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

I'll take them one at a time. If we plug a few values in for (f n) we can see how the function grows.

> (f 0)
0
> (f 1)
2
> (f 2)
4
> (f 3)
6
> (f 4)
8

It's pretty clear from these results that

f(n) = 2n

which is what we should expect from examining the given procedures.

(define (f n) (A 0 n))

(f n) just calls A with the x argument set to 0. The procedure for A has a condition defined just for this input.

((= x 0) (* 2 y))

Next, plugging in a few values for (g n) we get:

> (g 0)
0
> (g 1)
2
> (g 2)
4
> (g 3)
8
> (g 4)
16

This sequence is growing exponentially.

g(n) = 2ⁿ, when n > 0
g(n) = 0, when n = 0

Finally, plugging in values for (h n) we get:

> (h 0)
0
> (h 1)
2
> (h 2)
4
> (h 3)
16
> (h 4)
65536

This one had me scratching my head for a few minutes. If you evaluate (h 5) you'll see that it's a number so large that I won't even try to describe it. I didn't see a pattern in these results until I wrote them out in a slightly different way.

h(0) = 0
h(1) = 2 = 2¹
h(2) = 4 = 2²
h(3) = 16 = 2⁴
h(4) = 65536 = 2¹⁶

From these results I noticed that

h(n) = 2^h(n-1), when n > 1
h(1) = 2
h(0) = 0

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.