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)))))

• Inaimathi: Do you mind if I ask where you're getting these puzzles from? Based on the frequency with which one-letter function names/variables are defined, I'm assuming it's either a math book or a set of Haskell exercises. Have you considered something a bit more Lisp/Scheme oriented, if your goal is learning those languages specifically? This is ok for getting a grasp on theory, but I hope you're not planning on coding similarly out in the wild.
• C. K. Young: @Inaimathi: The questions appear to come from SICP, which is quite Scheme-orientated if you ask me!
• Inaimathi: That's a bit embarrassing; SICP is actually one of the ones I linked. To be fair, I skipped a bunch of it since I already watched the lectures by the time I started in on the book, but I honestly don't remember them putting in many single-letter function names.
• jaresty: Thanks, guys - indeed I am using SICP right now. Do you mind if I ask you to elaborate on what you think could be improved about my coding style here?

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.

• jaresty: Thanks for your help! I'm not familiar with letrec and do. Can you show me where to look up their usage?
• Adeel Zafar Soomro: @jaresty: Check out chapters four and five from the book The Scheme Programming Language by Dybvig.