Exercises from Section 1.2 of SICP

Here's a quick update from my ongoing study of SICP.

Exercise 1.9

I didn't have access to a scanner to show the results of my expansion, but my answer to the recursive or iterative question was: recursive. The inc function in the definition of + is deferred until the recursive call to + is complete, so the function has a linearly recursive shape.

Exercise 1.10

• (A (1 10)) ⇒ 1024
• (A (2 4)) ⇒ 65536
• (A (3 3)) ⇒ 65536
• (define (f n) (A 0 n)) ⇒ 2n
• (define (g n) (A 1 n)) ⇒ 2ⁿ
• (define (g n) (A 2 n)) ⇒ 2²ⁿ

Exercise 1.11

Recursive

(define (foo n)
  (cond ((< n 3) n)
        (else (+ (foo (- n 1)) (* 2 (foo (- n 2))) (* 3 (foo (- n 3)))))))

Iterative

There were a few false starts, but after Eli Bendersky's tip about solving the problem using a for loop, it all began to fall into place.

for Loop

function fooFor(n) {
    var a = 2;
    var b = 1;
    var c = 0;
    var result = n;
    for (i = 3; i <= n; i++) {
        result = a + 2*b + 3*c;
        c = b;
        b = a;
        a = result;
    }
    return result;
}

Tail-Recursion

(define (bar n)
  (cond ((< n 3) n)
        (else (bar-iter 2 1 0 n))))

(define (bar-iter a b c count)
  (cond ((= count 2) a)
        (else (bar-iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))

Back to flipping out…