src/sicp/ex1_10.clj

   1 (ns sicp.ex1_10
   2   (:use [sicp utils]
   3         [clojure.contrib trace test-is]))
   4
   5 ;; exercise 1.10
   6 ;; ackerman functions
   7 (defn A [x y]
   8   (cond (= y 0) 0
   9         (= x 0) (* 2 y)
  10         (= y 1) 2
  11         :else (A (- x 1)
  12                  (A x (- y 1)))))
  13
  14 ;; (comment
  15 ;; user> (A 1 10)
  16 ;; 1024
  17 ;; user> (A 2 4)
  18 ;; 65536
  19 ;; user> (A 3 3)
  20 ;; 65536
  21 ;; )
  22
  23 (defn f [n] (A 0 n)) ; f(n) = 2n
  24 (defn g [n] (A 1 n)) ; g(n) = 2^n
  25 ;; (comment
  26 ;;   g (n) = A (1,n)
  27 ;;         = A (0, A (1, n-1)) = f (A(1,n-1))
  28 ;;        = f (f (1,n-2))
  29 ;;          .....
  30 ;;          = f (f (f ... f (1,(n- (n-1)))))
  31 ;;            = f (f (f ... 2))
  32 ;;              = 2 * (2^(n-1))
  33 ;;                = 2^n
  34 ;; )
  35
  36 (defn h [n] (A 2 n)) ; h(n) = 2^(n^2)