# SICP - Solution: Exercise 1.11

##### October 2, 2018

## 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\geq3}$.

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 version:

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

Iterative version:

```
(define (f-iterative n)
(define (f-loop n-1 n-2 n-3 nth)
(if (= n nth)
n-1
(f-loop (+ n-1 (* 2 n-2) (* 3 n-3)) n-1 n-2 (+ 1 nth))))
(if (< n 3)
n
(f-loop 2 1 0 2)))
```