(use test)

(define r remainder)

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (r a b))))

(test 1 (gcd 5 7))
(test 2 (gcd 1024 386))
(test 3 (gcd 3 9))

;; ex 1.20

;; applicative order (omitting intermediate steps)
;; (gcd 206 40)
;; (gcd 40 (r 206 40)) <-
;; (gcd 40 6)
;; (gcd 6 (r 40 6)) <-
;; (gcd 6 4)
;; (gcd 4 (r 6 4)) <-
;; (gcd 4 2)
;; (gcd 2 (r 4 2)) <-
;; (gcd 2 0)
;; 2 <- remainder called 4 times

;; normal-order
;; (gcd 206 40)
;; (if (= 40 0)
;;     206
;;     (gcd 40 (r 206 40)))
;; (gcd 40 (r 206 40))
;; (if (= (r 206 40) 0) <-
;;     40
;;     (gcd (r 206 40) (r 40 (r 206 40))))
;; (if (= 6 0)
;;     40
;;     (gcd (r 206 40) (r 40 (r 206 40))))
;; (gcd (r 206 40) (r 40 (r 206 40)))
;; (if (= (r 40 (r 206 40)) 0) <<-
;;     (r 206 40)
;;     (gcd (r 40 (r 206 40))
;;          (r (r 206 40) (r 40 (r 206 40)))))
;; (if (= 4 0)
;;     (r 206 40)
;;     (gcd (r 40 (r 206 40))
;;          (r (r 206 40) (r 40 (r 206 40)))))
;; (gcd (r 40 (r 206 40))
;;      (r (r 206 40) (r 40 (r 206 40))))
;; (if (= (r (r 206 40) (r 40 (r 206 40))) 0) <<<<-
;;     (r 40 (r 206 40))
;;     (gcd (r (r 206 40) (r 40 (r 206 40)))
;;          (r (r 40 (r 206 40))
;;             (r (r 206 40) (r 40 (r 206 40))))))
;; (if (= 2 0)
;;     (r 40 (r 206 40))
;;     (gcd (r (r 206 40) (r 40 (r 206 40)))
;;          (r (r 40 (r 206 40))
;;             (r (r 206 40) (r 40 (r 206 40))))))
;; (gcd (r (r 206 40) (r 40 (r 206 40)))
;;      (r (r 40 (r 206 40))
;;         (r (r 206 40) (r 40 (r 206 40)))))
;; (if (= (r (r 40 (r 206 40))
;;           (r (r 206 40) (r 40 (r 206 40)))) <<<<<<<-
;;        0)
;;     (r (r 206 40) (r 40 (r 206 40)))
;;     (gcd (r (r 40 (r 206 40))
;;             (r (r 206 40) (r 40 (r 206 40))))
;;          (r (r (r 206 40) (r 40 (r 206 40)))
;;             (r (r 40 (r 206 40))
;;                (r (r 206 40) (r 40 (r 206 40)))))))
;; (if (= 0 0)
;;     (r (r 206 40) (r 40 (r 206 40)))
;;     (gcd (r (r 40 (r 206 40))
;;             (r (r 206 40) (r 40 (r 206 40))))
;;          (r (r (r 206 40) (r 40 (r 206 40)))
;;             (r (r 40 (r 206 40))
;;                (r (r 206 40) (r 40 (r 206 40)))))))
;; (r (r 206 40) (r 40 (r 206 40))) <<<<-
;; remainder called 18 times