• March 10, 2013

# SICP Exercise 1-11

##### Problem -

A function f is defined by the rule that

f(n) = n if n < 3 and

f(n) = f(n-1) + 2 * f(n-2) + 3 * f(n-3) if n >= 3.

Write a procedure that computes f by means of a recursive process.

Write a procedure that computes f by means of an iterative process.

##### Solution -

`Recursive solutions is very simple.`

``` scheme Recursive solution (define (f n) (if (< n 3) n (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

``````
`Iterative solution is a bit different.`

Base condition is same for iterative solution also. If n < 3, n is the

For n >= 3, we have to define a procedure which will evolve as a
iterative process.

For n >= 3, `f(n) = f(n-1) + 2 * f(n-2) + 3 * f(n-3)`

For n = 3, we have to evaluate above rule once. For n = 4, we have to
evaluate it twice. First to find out f(3) which then will be used to
find f(4).

So, it is clear that for n >= 3, we have to evaluate this rule `n - 2`
times. Lets name diff to (n - 2).

Now lets consider state variables which will hold all the information
to find solution at a particular instance in this process.

For n = 3, we need f(0), f(1) and f(2) to find out f(3).
They are respectively 0, 1 and 2.

Lets name them a = 0, b = 1 and c = 2.

Now answer in each iteration is `3 * a + 2 * b + c`

This answer needs to be passed to recursive call till diff is 0.

So after each iteration, state variables are changed as follows:

`b becomes a`

`c becomes b`

`3 * a + 2 * b + c becomes c`

`diff becomes diff - 1`

For n = 3, initially, a = 0, b = 1, c = 2 and diff = 3 - 2 = 1,

After one iteration, a = 1, b = 2, c = 4 and diff = 0

Now, base condition is when diff = 0, c is the answer. So here for

Lets repeat this for f(4)

n > 3

diff = 4 - 2 = 2

a = 0, b = 1, c = 2

After first iteration,

diff = 2 - 1 = 1

a = 1, b = 2, c = (3 * 0 + 2 * 1 + 2) = 4

diff > 0 So second iteration will be called

After second iteration,

diff = 1 - 1 = 0

a = 2, b = 4, c = (3 * 1 + 2 * 2 + 4) = 11

Now diff = 0, so c is the answer.

f(4) = 11

The implementation of this process is recursive as shown below. But
the `process which is evolved is iterative.`

``` scheme iterative-solution

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

(define (f-iter a b c diff)
(if (= diff 0)
c
(f-iter b c (+ (* 3 a) (* 2 b) c) (- diff 1))))
``````

Iterative process evloved for f(4)

``````
;; (f 4)
;; (f-iter 0 1 2 2)
;; (f-iter 1 2 4 1)
;; (f-iter 2 4 11 0)
;; 11
``````