; catalan numbers

(define (choose n k)
  (if (zero? k) 1
    (* n (/ k) (choose (- n 1) (- k 1)))))

(define (catalan n)
  (if (zero? n) 1
    (- (choose (+ n n) n) (choose (+ n n) (- n 1)))))

(do ((i 0 (+ i 1))) ((< 30 i))
  (display i) (display #\tab)
  (display (catalan i)) (newline))

(define-syntax define-memoized
  (syntax-rules ()
    ((define-memoized (f arg ...) body ...)
      (define f
        (let ((cache (list)))
          (lambda (arg ...)
            (cond ((assoc `(,arg ...) cache) => cdr)
            (else (let ((val (begin body ...)))
                    (set! cache (cons (cons `(,arg ...) val) cache))
                    val)))))))))

(define-memoized (catalan n)
  (if (zero? n) 1
    (let loop ((i 1) (count 0))
      (if (< n i) count
        (loop (+ i 1) (+ count (* (catalan (- i 1))
                                  (catalan (- n i)))))))))

(do ((i 0 (+ i 1))) ((< 30 i))
  (display i) (display #\tab)
  (display (catalan i)) (newline))