# 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
answer.
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
f(3), 4 is the answer.
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
```