SICP Exercise 1.11

Question

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\ge 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.

Answer

The recursive implementation probably does not need much explanation, as it is fairly straightforward:

copy(define (rec n)
  (cond ((< n 3) n)
		(else (+ (rec (- n 1)) (* 2 (rec (- n 2))) (* 3 (rec (- n 3)))))))

For the iterative implementation, we need to keep track of state somehow. In particular, we are using the variable a to track the result of the current iteration, b to track the result of the last iteration, and c to track the result of the penultimate iteration. Since $f(n)$ returns $n$ for $n<3$, we can populate these values with 2, 1, and 0 respectively. This is the equivalent of starting the function at $n=3$. We then pass n as the counter variable to keep count of the function iterations.

copy(define (iter n)
  (define (iter-c a b c counter)
    (cond ((< counter 3) a)
  	      (else (iter-c (+ a (* 2 b) (* 3 c)) a b (- counter 1)))))
  (iter-c 2 1 0 n))