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)