**Exercise 1.11:** A function `f`

is defined by the rule that f(n) = n if n<3 and
f(n) = f(n - 1) + 2f(n - 2) + 3f(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.

The idea is to use a triple of integers a,b,c initialized to f(2) = 2 f(1) = 1 and f(0) = 0, and to repeatedly apply the simultaneous transformations

$$ a \leftarrow a + 2b + 3c $$

a is now f(n)

$$ b \leftarrow a $$

b is now f(n-1)

$$ c \leftarrow b $$

c is now f(n-2)

This is nothing but a slightly more complex Fibonacci iteration example from earlier.

F(n) = F(n-1) + F(n-2) where F(n) = n if n<2

$$ F_n = F_{n-1} + F_{n-2} $$

$$ a \leftarrow a + b $$

a is now F(n)

$$ b \leftarrow a $$

b is now F(n-1)

Recursive implementation of f(n) is straightforward:

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

```
> (f-rec 1)
1
> (f-rec 3)
4
> (f-rec 6)
59
> (f-rec 8)
335
```

Iterative implementation of f(n)

```
(define (f n)
(f-iter 2 1 0 n))
(define (f-iter a b c count)
(cond ((< count 2) count)
((= count 2) a)
(else
(f-iter (+ a (* 2 b) (* 3 c))
a
b
(- count 1)))))
```

```
> (f 1)
1
> (f 3)
4
> (f 6)
59
> (f 8)
335
```