(define fibonacci
  (lambda (n)
    (if (or (zero? n) (= n 1))
        1
        (+ (fibonacci (- n 2)) (fibonacci (- n 1))))))
 
; Next, the memoized version of fibonacci.  In a classic space/time 
; tradeoff, we keep track of all previously-computed values of the function,
; so we can simply look them up the next time they are needed, rather than
; having to recompute them.
;
; Note that (assq item lyst) assumes that lyst is a list of pairs.  It
; returns the first pair in lyst whose car is eq? to item. If there is no
; such pair, it returns ().
 
(define fib-memo
  (let ([max 1]
        [sofar '((1 . 1) (0 . 1))])
    (lambda (n)
      (if (<= n max)
          (cdr (assq n sofar))
          (let* ([v1 (fib-memo (- n 1))]
                 [v2 (fib-memo (- n 2))]
                 [v3 (+ v2 v1)])
            (set! max n)
            (set! sofar (cons (cons n v3) sofar))
            v3)))))
 
(define time-fib (lambda (n) (collect) (time (fibonacci n))))
 
(define time-memo (lambda (n) (collect) (time (fib-memo n))))