Linear Operators and Recursion

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.

Solution

For both the recursive definition, and especially for the iterative definition, it is instructive to consider the linear operator that defines f.

In the case of Fibonacci numbers, the linear operator is given by:

We can use this information to build the iterative procedure:

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b n)
 (if (= n 0)
     b
     (fib-iter (+ a b) a (- n 1))))

Similarly, we can specify the linear operator A that defines the function f:

In a similar way, we can use this information to specify the following procedure:

(define (f n)
 (if (< n 3)
     n
     (f-iter 2 1 0 n)))

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

Home