SICP Exercise 1.11 – Writing a Procedure

In this exercise, we are asked to write a procedure to compute the function f:

f(n) = n, n < 3
f(n) = f(n-1) + 2*f(n-2) + 3*f(n-3), n ≥ 3

A procedure that computes f by means of a recursive process is easy and can be written as:

(define (f n) 
  (if (< n 3) n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))

To write an iterative procedure, we observe that for the computation of , only the values of , and are needed. Leveraging this, we can write an iterative procedure where these three values are passed as arguments:

(define (f n)
  (if (< n 3) n
      (f-iter 2 1 0 (- n 2))))

(define (f-iter n1 n2 n3 left)
  (if (= left 0) n1
      (f-iter (+ n1 (* 2 n2) (* 3 n3))
              n1
              n2
              (- left 1))))