Exercise 1.11

The Question

A function \(f\) is defined by the rule that

\[f(n) = \begin{cases} n & \text{if n < 3} \\ f(n - 1) + 2f(n - 2) + 3f(n - 3) & \text{if n} \ge 3 \\ \end{cases}\]

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 Answer

Recursive Implementation

The rule directly spells out our recursive implementation:

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

Testing it out:

(f 2)
2

(f 3)
4

(f 10)
1892

Iterative Implementation

To implement \(f(n)\) iteratively, we can use the same principle as fib-iter and pass \(f(n - 1)\), \(f(n - 2)\) and \(f(n - 3)\) as parameters and transform them in each iteration, working upwards to \(n\) from \(3\).

we use the integers \(a\), \(b\) and \(c\) to represent \(f(n - 1)\), \(f(n - 2)\) and \(f(n - 3)\), and initialize them as \(f(2) = 2\), \(f(1) = 1\) and \(f(0) = 0\). We then apply the following transformations successively:

\[\begin{align*} a &\leftarrow a + 2b + 3c \\ b &\leftarrow a \\ c &\leftarrow b \\ \end{align*}\]

This gives us the following iterative process:

(define (f n)
  (define (iter a b c counter)
    (if (> counter n)
        a
        (iter (+ a (* 2 b) (* 3 c)) a b (+ counter 1))))
  (if (< n 3)
      n
      (iter 2 1 0 3)))

Testing it out, we get the same results:

(f 2)
2

(f 3)
4

(f 10)
1892

Comments