2
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.