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.First, the recursive process.
(define (fun-r n)
(if (< n 3)
n
(+ (* 3 (fun-r (- n 3)))
(* 2 (fun-r (- n 2)))
(fun-r (- n 1)))))
This was surprisingly straightforward. I thought recursion was hard, but this felt natural. Even more surprising was how hard the iterative version was. I puzzled on it for a while. I finally figured it out aftter I referred back to the discussion of the iterative Fibonnacci procedure in the text.
I'll need to keep three variables and apply the following transformations in each step of the iteration:
a ← a + b + c
b ← a
c ← b
After applying the transformation n times, the results will be
a = f (n + 2)
b = f (n + 1)
c = f (n)
I'll start the process off by initializing the first three terms at 2, 1, 0. The final procedure follows.
(define (fun-iter a b c count)
(if (= count 0)
c
(fun-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))
(define (fun n)
(fun-iter 2 1 0 n))
