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

OyBjYXRhbGFuIG51bWJlcnMKCihkZWZpbmUgKGNob29zZSBuIGspCiAgKGlmICh6ZXJvPyBrKSAxCiAgICAoKiBuICgvIGspIChjaG9vc2UgKC0gbiAxKSAoLSBrIDEpKSkpKQoKKGRlZmluZSAoY2F0YWxhbiBuKQogIChpZiAoemVybz8gbikgMQogICAgKC0gKGNob29zZSAoKyBuIG4pIG4pIChjaG9vc2UgKCsgbiBuKSAoLSBuIDEpKSkpKQoKKGRvICgoaSAwICgrIGkgMSkpKSAoKDwgMzAgaSkpCiAgKGRpc3BsYXkgaSkgKGRpc3BsYXkgI1x0YWIpCiAgKGRpc3BsYXkgKGNhdGFsYW4gaSkpIChuZXdsaW5lKSkKCihkZWZpbmUtc3ludGF4IGRlZmluZS1tZW1vaXplZAogIChzeW50YXgtcnVsZXMgKCkKICAgICgoZGVmaW5lLW1lbW9pemVkIChmIGFyZyAuLi4pIGJvZHkgLi4uKQogICAgICAoZGVmaW5lIGYKICAgICAgICAobGV0ICgoY2FjaGUgKGxpc3QpKSkKICAgICAgICAgIChsYW1iZGEgKGFyZyAuLi4pCiAgICAgICAgICAgIChjb25kICgoYXNzb2MgYCgsYXJnIC4uLikgY2FjaGUpID0+IGNkcikKICAgICAgICAgICAgKGVsc2UgKGxldCAoKHZhbCAoYmVnaW4gYm9keSAuLi4pKSkKICAgICAgICAgICAgICAgICAgICAoc2V0ISBjYWNoZSAoY29ucyAoY29ucyBgKCxhcmcgLi4uKSB2YWwpIGNhY2hlKSkKICAgICAgICAgICAgICAgICAgICB2YWwpKSkpKSkpKSkKCihkZWZpbmUtbWVtb2l6ZWQgKGNhdGFsYW4gbikKICAoaWYgKHplcm8/IG4pIDEKICAgIChsZXQgbG9vcCAoKGkgMSkgKGNvdW50IDApKQogICAgICAoaWYgKDwgbiBpKSBjb3VudAogICAgICAgIChsb29wICgrIGkgMSkgKCsgY291bnQgKCogKGNhdGFsYW4gKC0gaSAxKSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChjYXRhbGFuICgtIG4gaSkpKSkpKSkpKQoKKGRvICgoaSAwICgrIGkgMSkpKSAoKDwgMzAgaSkpCiAgKGRpc3BsYXkgaSkgKGRpc3BsYXkgI1x0YWIpCiAgKGRpc3BsYXkgKGNhdGFsYW4gaSkpIChuZXdsaW5lKSk=