Both an Iterative and a Recursive f(x)

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>=3. Write a recursive and an iterative process for computing f(n).

I wrote the following:

(define (f_r n)
  ; recursive
  (cond ((< n 3) n)
        (else (+ (f_r (- n 1)) 
                 (* 2 (f_r (- n 2))) 
                 (* 3 (f_r (- n 3)))))))

(define (f_i n)
  ;iterative
  (f_i-prime 1 0 0 n))

(define (f_i-prime n n-1 n-2 count)
  (cond ((= count 0) n)
        ((f_i-prime (+ n n-1 n-2) 
                    (+ n n-1) 
                    n-1 
                    (- count 1)))))

What do you think?

EDIT 1: Since my first iterative solution was erroneous, here is a corrected version:

(define (f_i n)
  ;iterative
  (f_i-prime 2 1 0 n))

(define (f_i-prime f_x+2 f_x+1 f_x n-x)
  (cond ((= n-x 0) f_x)
        ((f_i-prime (+ f_x+2 (* 2 f_x+1) (* 3 f_x) )
                    f_x+2 
                    f_x+1 
                    (- n-x 1)))))

Answer 1

Your iterative definition will not produce correct results for most values of n.

When rewriting a pure recursive function as an iterative one, one needs to keep as many accumulators as there are base cases. In the iterative step, compute the next value, store it in the first accumulator, rotate the values of all remaining accumulators and decrement the loop variable.

Here's an implementation in your style:

(define (f_i n)
  ;iterative
  ;initial values of accumulators are f(2) = 2, f(1) = 1 and f(0) = 0; loop variable is n.
  (f_i-prime 2 1 0 n))

(define (f_i-prime f-x+2 f-x+1 f-x n-x)
  (cond ((= n-x 0) f-x)   ; if n-x = 0, then n = x, so return f(x) = f(n).
        ((f_i-prime (+ f-x+2 (* 2 f-x+1) (* 3 f-x))   ; iterative step -- compute next value of f(x + 2);
                    f-x+2                             ; ... rotate all other accumulators;
                    f-x+1
                    (- n-x 1)))))                     ; ... and decrement loop variable.

One may incorporate the helper function within the main function using letrec as follows (this version differs slightly from the previous one in that the loop variable counts up from 0 to n):

(define (f-iterative n)
  (letrec
      ((f-aux
        (lambda (x f-x+2 f-x+1 f-x)
          (cond
            ((= x n) f-x)
            ((f-aux (+ x 1) (+ f-x+2 (* 2 f-x+1) (* 3 f-x)) f-x+2 f-x+1))))))
    (f-aux 0 2 1 0)))

One may also use the do expression to write the iterative version as follows:

(define (f-iterative n)
  (do
      ((x 0 (+ x 1))
       (f-x+2 2 (+ f-x+2 (* 2 f-x+1) (* 3 f-x)))
       (f-x+1 1 f-x+2)
       (f-x 0 f-x+1))
    ((= x n) f-x)))

As to your recursive definition, you may wish to memoize the results in order to decrease your algorithm's complexity, which is currently in O(3 ^ n). Memoization will improve that to linear complexity.