SICP - exercise 1.11 - tree recursion

Question

From SICP

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.

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 (< 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?

Answer 1

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 (< 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:

1. If the auxiliary function is defined inside f, the execution is 30-35% faster (and I think this is also stylistically better!)

2. 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 (< 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!