sicp-ex-1.11


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)

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

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