SICP - exercise 1.11 - tree recursion From SICP


  Exercise 1.11: A function \$f\$ is defined by the rule that: 
  
  \$f(n) = n\$ if \$n &lt; 3\$, and 
  
  \$f(n) = f(n-1)+2f(n-2)+3f(n-3)\$ if \$n &gt;= 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.
  


Please review my code.

I think the recursive process is obvious enough but I put it here just in case it could be improved.

(define (f n)
  (if (&lt; n 3) n
        (+ (f (- n 1))
                 (* 2 (f (- n 2)))
                 (* 3 (f (- n 3))))))


Now, here's the iterative process. I followed the relationship created by the fibonacci example. The idea is:


\$a = f(n+2)\$
\$b = f(n+1)\$
\$c = f(n)\$


(define (f n) 
  (f-iter 2 1 0 n))

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


How to make this code better and faster? Are there more efficient ways?
Before looking for efficiency, note that there is a logical error in the tail recursive version of your function: it does not terminate on negative values (while the first function does terminate). 

A way of correcting this error is simply to perform the check before calling f-iter. For instance:

(define (f n)
  (if (&lt; n 3)
      n
      (f-iter 2 1 0 n)))

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


From the efficiency point a view, I performed a few (unscientific) tests in DrRacket and noticed the following facts:


If the auxiliary function is defined inside f, the execution is 30-35% faster (and I think this is also stylistically better!)
An additional speedup of 20-40% can be gained if we reverse the counter, making it starting from 0 and going to n.


The differences in execution times where noticeable with n greater than 15000.

And so this is the more efficient version according to those tests:

(define (f n) 
  (define (f-iter a b c count)
    (if (= count n)
        c
        (f-iter (+ a (* 2 b) (* 3 c)) a b (+ count 1))))
  (if (&lt; n 3)
      n
      (f-iter 2 1 0 0)))


Of course these differences can be accounted only to the compiler, not to a change of the algorithm, so that by using another compiler maybe no differences could be found, or they could even be reversed!