SICP Exercise 1.11: Recursive and Iterative Functions

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.

The description implies that we have two cases to deal with, depending upon whether n is less than 3 or not. For both the recursive and iterative procedures we can achieve this with an if conditional to separate the two cases, and have the consequent to return n. However it's in the alternative where the two procedures will differ.

For the recursive procedure, the alternative is achieved via a direct translation of the function for n ≥ 3, performing the appropriate recursive calls of f and combining the results as defined:

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

Let's look at the results of this:

> (f 0)
0
> (f 1)
1
> (f 2)
2
> (f 3)
4
> (f 4)
11
> (f 5)
25
> (f 6)
59

For the iterative approach we need to accumulate the result as we go. To do this we can observe that, for any value of n ≥ 3, we need to know the result of (f n) for the preceding 3 values of n. We know what these are for n = 3: {0, 1, 2}. So we can start with that as our base case. Then all we need to do is, for each increasing value of n check to see if we've reached our target yet. If so then the third value in this set is the result; if not then we can calculate the next value in the sequence by plugging these three values into the formula, generate the next set by dropping the first item, and appending the newly calculated value as the new third item and loop again.

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

Notice how this implementation will always perform at least two calls to iter:

• Evaluating (f 3) requires evaluating (iter 0 1 2 2).
• The predicate for (iter 0 1 2 2) evaluates to false.
• This causes the alternative to be evaluated, and so (iter 1 2 4 3) is evaluated.
• This time the predicate evaluates to true and the result is returned.

Given that we only ever try to evaluate iter if n ≥ 3, we could remove the first of these iterations by starting the iteration with the appropriate values for n = 3. I.e. {1, 2, 4}:

(define (f n)
  (define (iter a b c count)
    (if (= count n)
        c
        (iter b c (+ c (* 2 b) (* 3 a)) (+ count 1))))
  (if (< n 3)
      n
      (iter 1 2 4 3)))

This gives the same output as before - I did check, honest! I'll not bother repeating it though.