views:

311

answers:

5

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

+2  A: 

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.

Charlie
+1  A: 

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.

Adam Rosenfield
Thanks for the link. Its very well articulated and coded.
Amit
+7  A: 

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.

yjerem
Nice solution, very pretty.
Darren Clark
Argh. No wonder I wasn't able to get results... I was rotating the results backwards--my recursive call was (f-iter (*...) b a ...) instead of a b >_<. Thanks.
Tordek
Hello Jeremy, thanks for working it out for me. But, what I was looking for has been suggested by Charlie below.
Amit
It's also idiomatic in scheme to define local functions for this purpose, especially using named let when writing loops. For example: (define (fib n) (let fib-iter ((a 1) (b 0) (count n)) (if (= count 0) b (fib-iter (+ a b) a (- count 1)))))
Aaron
+1  A: 

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.

Jack Gray
Hello Jack. Even without the "EDIT", thanks for your suggestion. I have been re-learning "Recurrence Eqns." and your suggestion helped me to think about it a bit more.
Amit
A: 

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)))
finnw