1.11

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.

Recursive process

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

(f 0)

(f 1)

(f 2)

(f 3)

Iterative process

Use a tuple of integers a and b and c, initialized to $f(0) = 0$, $f(1) = 1$, and $f(2) = 2$, and to repeatedly apply the simultaneous transformations

a <- a + b + c
b <- a
c <- b

It is not head to show that, after applying this transformation n times, a, b, and c will be equal, respectively, to $f(n+2)$, $f(n+1)$ and $f(n)$. Thus, we can compute $f(n)$ iteratively using the procedure

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

(f 0)

(f 1)

(f 2)

(f 3)