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 f(n), only the values of f(n-1), f(n-2) and f(n-3) 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))))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s