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)) ⇒ 2n
(define (g n) (A 2 n)) ⇒ 22n
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…