;; naively compute the nth Fibonacci number,
;; where n is non-negative
(define f
  (lambda (n)
    (if (< n 2)
        n
        (+ (f (- n 1))
           (f (- n 2))))))

;; compute the nth Fibonacci number using memoization
(define mf
  (lambda (n)
    (let ((T (make-vector (+ n 1))))
      (define f
        (lambda (i)
          (if (not (vector-ref T i))
              (vector-set! T i
                           (if (< i 2)
                               i
                               (+ (f (- i 1))
                                  (f (- i 2))))))
          (vector-ref T i)))
      (vector-fill! T #f)
      (f n))))

;; compute choose(n, k) naively
(define choose
  (lambda (n k)
    (cond ((zero? k) 1)
          ((= n k) 1)
          (else (+ (choose (- n 1) k)
                   (choose (- n 1) (- k 1)))))))

(load "2d-table.scm")

;; compute choose(n, k) using memoization
(define mchoose
  (lambda (n k)
    (let ((T (make-table (+ n 1) (+ k 1))))
      (define choose
        (lambda (i j)
          (if (not (table-ref T i j))
              (table-set! T i j
                           (cond ((zero? j) 1)
                                 ((= i j) 1)
                                 (else (+ (choose (- i 1) j)
                                          (choose (- i 1) (- j 1)))))))
          (table-ref T i j)))
      (table-fill! T #f)
      (choose n k))))