**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 is now f(n)

b is now f(n-1)

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
[latex]F_n = F_{n-1} + F_{n-2}[/latex]
[latex]a \leftarrow a + b [/latex]
a is now F(n)
[latex]b \leftarrow a [/latex]
b is now F(n-1)
Recursive implementation of f(n) is straightforward:

1 2 3 4 |
(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)

1 2 3 4 5 6 7 8 9 10 |
(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*