# 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 < 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.

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?

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!