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

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