<< Previous exercise (1.10) | sicp-solutions | Next exercise (1.12) >>

The recursive implementation of the given function is straighforward: just translate the definition into Scheme code.

;; ex 1.11. Recursive implementation. (define (f n) (cond ((< n 3) n) (else (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))))

The iterative implementation requires a bit of thought. Note that the solution presented here is somewhat wasteful, since it computes `f(n+1)` and `f(n+2)`.

;; ex 1.11. Iterative implementation (define (f n) (define (iter a b c count) (if (= count 0) a (iter b c (+ c (* 2 b) (* 3 a)) (- count 1)))) (iter 0 1 2 n))

;; Testing (f 0) (f 1) (f 2) (f 3) (f 4) (f 5) (f 6)

The above version does not terminate for n < 0. The following implementation does:

(define (f n) (fi n 0 1 2)) (define (fi i a b c) (cond ((< i 0) i) ((= i 0) a) (else (fi (- i 1) b c (+ c (* 2 b) (* 3 a))))))

Another implementation, which does not calculate `f(n+1)` or `f(n+2)`.

```
(define (foo n)
(define (foo-iter a b c n)
;; a = f(n - 1), b = f(n - 2), c = f(n - 3).
;; return a + 2b + 3c
(if (< n 3)
a
(foo-iter (+ a (* 2 b) (* 3 c)) a b (- n 1))))
(if (< n 3)
n
(foo-iter 2 1 0 n)))
```

Output

> (foo 0) 0 > (foo 1) 1 > (foo 2) 2 > (foo 3) 4 > (foo 4) 11 > (foo 5) 25 > (foo 6) 59 > (foo 7) 142

Another iterative version, similar to above, but counting up from 3 to n (instead of counting down).

(define (f n) ;; Track previous three values. ;; fi-1 is f(i-1) ;; fi-2 is f(i-2) ;; fi-3 is f(i-3) (define (f-iter fi-1 fi-2 fi-3 i) ;; Calculate value at current index i. (define fi (+ fi-1 (* 2 fi-2) (* 3 fi-3))) (if (= i n) fi (f-iter fi fi-1 fi-2 (+ i 1)))) (if (< n 3) n (f-iter 2 1 0 3))) ;; start index i=3, count up until reach n.

Here is another iterative version that the original poster called "a little bit different".

Another commenter pointed out that it gives wrong answers for n < 3, but also asked, could someone explain how this works for larger inputs?

I am not the original author, but after staring at this for a while, I think I can explain it and correct it for n < 3.

Original version:

```
(define (f n)
(define (f-iter n a b c)
;; this makes f(n) = a f(2) + b f(1) + c f(0) for integer n.
(if (< n 4)
;; N < 4. cause n-1 < 3
(+ (* a (- n 1) )
(* b (- n 2))
(* c (- n 3)))
(f-iter (- n 1) (+ b a) (+ c (* 2 a)) (* 3 a))))
(f-iter n 1 2 3))
```

Explanation:

The other iterative versions start from f(0), f(1), and f(2), and calculate the next f(i) *value* based on the previous values.

In contrast, this version tracks just the *coefficients* of f(n-1), f(n-2), f(n-3). It starts with coefficients (a, b, c) = (1, 2, 3), as given by the definition. It then expands f(n) in terms of f(n-1), f(n-2), f(n-3). And so on, until you get the equivalent value using coefficients for f(2), f(1), f(0).

In f-iter, n is the counter that starts at the given n and gets decremented until n = 3. The `if` statement causes execution to stop at n = 3, and return this expression:

```
(+ (* a (- n 1)) (* b (- n 2)) (* c (- n 3)))
```

Since n is always 3 at this point (ignore the failure cases of n < 3 for now), that expression is basically:

```
(+ (* a (- 3 1)) (* b (- 3 2)) (* c (- 3 3)))
```

which is:

```
(+ (* a 2) (* b 1) (* c 0))
```

And that satisfies the objective of giving the answer in terms of coefficients of f(2), f(1), f(0):

```
(+ (* a f(2)) (* b f(1)) (* c f(0)))
```

So that is why inputs 3 or larger works, while n < 3 fails. For n < 3, the function should just return n, rather than calculate coefficients.

Corrected version:

```
(define (f n)
;; Given starting coefficients (a, b, c) = (1, 2, 3),
;; where f(n) = 1 f(n-1) + 2 f(n-2) + 3 f(n-3),
;; f-iter calculates new (a, b, c) such that
;; f(n) = a f(2) + b f(1) + c f(0),
;; where integer n > 3.
(define (f-iter n a b c)
(if (= n 3)
(+ (* a 2) ;; f(2) = 2
(* b 1) ;; f(1) = 1 ;; (* b 1) = b, and
(* c 0)) ;; f(0) = 0 ;; (* c 0) = 0, which can be omitted,
;; but shown here for completeness.
(f-iter (- n 1) ;; decrement counter
(+ b a) ;; new-a = a + b
(+ c (* 2 a)) ;; new-b = 2a + c
(* 3 a)))) ;; new-c = 3a
;; main body
(if (< n 3)
n
(f-iter n 1 2 3)))
```

At each step of f-iter for n larger than 3, f-iter calls itself with new values for a, b, and c:

new-a = a + b new-b = 2a + c new-c = 3a

To see where those calculations come from, consider this example of how (f 5) calculates 25.

(f 5) (f-iter 5 1 2 3) n=5, f(5) = 1 f(4) + 2 f(3) + 3 f(2) ;; by definition = 1 (1 f(3) + 2 f(2) + 3 f(1)) + 2 f(3) + 3 f(2) ;; expand f(4) = (1 + 2) f(3) + (2 + 3) f(2) + 3 f(1) ;; combine terms a + b 2a + c 3a ;; observe pattern = 3 f(3) + 5 f(2) + 3 f(1) ;; new a b c (f-iter 4 3 5 3) n=4, = 3 f(3) + 5 f(2) + 3 f(1) ;; continued = 3 (1 f(2) + 2 f(1) + 3 f(0)) + 5 f(2) + 3 (f1) ;; expand f(3) = (3 + 5) f(2) + (6 + 3) f(1) + 9 f(0) ;; combine terms a + b 2a + c 3a ;; observe pattern = 8 f(2) + 9 f(1) + 9 f(0) ;; new a b c (f-iter 3 8 9 9) n=3, = 8 f(2) + 9 f(1) + 9 f(0) ;; n=3, so stop looping, and apply a, b, c: (+ (* a 2) (* b 1) (* c 0)) (+ (* 8 2) (* 9 1) (* 9 0)) (+ 16 9 0) 25

Heres another iterative solution, counting up

```
(define (fn-iterate n)
(define (fn-iter count n f1 f2 f3)
(if (= count n) f3 (fn-iter (+ count 1) n f2 f3 (+ (* 3 f1) (* 2 f2) f3))))
(if (<= n 3) n (fn-iter 3 n 1 2 3)))
```