;; The old Theta(2^n) way....

(define (fibs n)
  (if (< n 2)
      n
      (+ (fibs (- n 1))
	 (fibs (- n 2)))))

;; The memoized Theta(n) way!  Things are faster because
;; we just compute each of fib1, fib2, ... , fibn once!

(define (fast-fibs n)
  (memo-fib n (make-vector (+ n 1) #f)))

(define (memo-fib n table)
  (if (< n 2)
      n
      (let ((old (vector-ref table n)))
	(if (number? old)
	    old
	    (begin
	      (vector-set! table n (+ (memo-fib (- n 1) table)
				      (memo-fib (- n 2) table)))
	      (vector-ref table n))))))