How to improve this piece of code?

Question

My solution to exercise 1.11 of SICP is:

(define (f n)
  (if (< n 3)
   n
   (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
   ))

As expected, a evaluation such as (f 100) takes a long time. I was wondering if there was a way to improve this code (without foregoing the recursion), and/or take advantage of multi-core box. I am using 'mit-scheme'.

Answer 1

I'm not sure how best to code it in Scheme, but a common technique to improve speed on something like this would be to use memoization. In a nutshell, the idea is to cache the result of f(p) (possibly for every p seen, or possibly the last n values) so that next time you call f(p), the saved result is returned, rather than being recalculated. In general, the cache would be a map from a tuple (representing the input arguments) to the return type.

Answer 2

The exercise tells you to write two functions, one that computes f "by means of a recursive process", and another that computes f "by means of an iterative process". You did the recursive one. Since this function is very similar to the fib function given in the examples of the section you linked to, you should be able to figure this out by looking at the recursive and iterative examples of the fib function:

; Recursive
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

; Iterative
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

In this case you would define an f-iter function which would take a, b, and c arguments as well as a count argument.

Here is the f-iter function. Notice the similarity to fib-iter:

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

And through a little trial and error, I found that a, b, and c should be initialized to 2, 1, and 0 respectively, which also follows the pattern of the fib function initializing a and b to 1 and 0. So f looks like this:

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

Note: f-iter is still a recursive function but because of the way Scheme works, it runs as an iterative process and runs in O(n) time and O(1) space, unlike your code which is not only a recursive function but a recursive process. I believe this is what the author of Exercise 1.1 was looking for.

Answer 3

Well, if you ask me, think like a mathematician. I can't read scheme, but if you're coding a Fibonacci function, instead of defining it recursively, solve the recurrence and define it with a closed form. For the Fibonacci sequence, the closed form can be found here for example. That'll be MUCH faster.

edit: oops, didn't see that you said forgoing getting rid of the recursion. In that case, your options are much more limited.

Answer 4

See this article for a good tutorial on developing a fast Fibonacci function with functional programming. It uses Common LISP, which is slightly different from Scheme in some aspects, but you should be able to get by with it. Your implementation is equivalent to the bogo-fig function near the top of the file.

Answer 5

To put it another way:

To get tail recursion, the recursive call has to be the very last thing the procedure does.

Your recursive calls are embedded within the * and + expressions, so they are not tail calls (since the * and + are evaluated after the recursive call.)

Jeremy Ruten's version of f-iter is tail-recursive rather than iterative (i.e. it looks like a recursive procedure but is as efficient as the iterative equivalent.)

However you can make the iteration explicit:

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

or

(define (f n)
  (do
    ((a 2 (+ a (* 2 b) (* 3 c)))
     (b 1 a)
     (c 0 b)
     (count n (- count 1)))
    ((<= count 0) c)))

Answer 6

That particular exercise can be solved by using tail recursion - instead of waiting for each recursive call to return (as is the case in the straightforward solution you present), you can accumulate the answer in a parameter, in such a way that the recursion behaves exactly the same as an iteration in terms of the space it consumes. For instance:

(define (f n)
  (define (iter a b c count)
    (if (zero? count)
        c
        (iter (+ a (* 2 b) (* 3 c))
              a
              b
              (- count 1))))
  (if (< n 3)
      n
      (iter 2 1 0 n)))