sicp-1-2-5-greatest-common-divisors

#lang racket

;; 1.20

(define (my-gcd a b)
  (if (zero? b)
    a
    (my-gcd b (remainder a b))))

;; how many remainder operations are performed during the normal-order evaluation
;; of (my-gcd 206 40)?

(my-gcd 206 40)

(if (= 40 0) 206 (my-gcd 40 (remainder 206 40)))

(my-gcd 40 (remainder 206 40))

(if (= (remainder 206 40) 0) ; predicate evaluates one remainder
  40
  (my-gcd (remainder 206 40)
          (remainder 40 (remainder 206 40))))

(my-gcd (remainder 206 40)
        (remainder 40 (remainder 206 40)))

(if (= (remainder 40 (remainder 206 40)) 0) ; predicate evaluates two remainders
  (remainder 206 40)
  (my-gcd (remainder 40 (remainder 206 40))
          (remainder (remainder 206 40)
                     (remainder 40 (remainder 206 40)))))

(my-gcd (remainder 40 (remainder 206 40))
        (remainder (remainder 206 40)
                   (remainder 40 (remainder 206 40))))

(if (= (remainder (remainder 206 40)
                  (remainder 40 (remainder 206 40))) ; four remainders
       0)
  (remainder 40 (remainder 206 40))
  (my-gcd (remainder (remainder 206 40)
                     (remainder 40 (remainder 206 40)))
          (remainder (remainder 40 (remainder 206 40))
                     (remainder (remainder 206 40)
                                (remainder 40 (remainder 206 40))))))

(my-gcd (remainder (remainder 206 40)
                   (remainder 40 (remainder 206 40)))
        (remainder (remainder 40 (remainder 206 40))
                   (remainder (remainder 206 40)
                              (remainder 40 (remainder 206 40)))))

(if (= (remainder (remainder 40 (remainder 206 40))
                  (remainder (remainder 206 40)
                             (remainder 40 (remainder 206 40)))) ; seven remainders
       0)
  (remainder (remainder 206 40)
             (remainder 40 (remainder 206 40)))
  (my-gcd (remainder (remainder 40 (remainder 206 40))
                     (remainder (remainder 206 40)
                                (remainder 40 (remainder 206 40))))
          (remainder (remainder (remainder 206 40)
                                (remainder 40 (remainder 206 40)))
                     (remainder (remainder 40 (remainder 206 40))
                                (remainder (remainder 206 40)
                                           (remainder 40 (remainder 206 40)))))))

(remainder (remainder 206 40)
           (remainder 40 (remainder 206 40))) ; four remainders evaluated

2

;; so noe evaluated remainder 1 + 2 + 4 + 7 + 4 = 18 times

;; how many remainder operations are performed during the applicative-order
;; evaluation of (my-gcd 206 40)?

(my-gcd 206 40)
(my-gcd 40 (remainder 206 40))
(my-gcd 40 6)
(my-gcd 6 (remainder 40 6))
(my-gcd 6 4)
(my-gcd 4 (remainder 6 4))
(my-gcd 4 2)
(my-gcd 2 (remainder 4 2))
(my-gcd 2 0)
2

;; aoe evaluated remainder only 4 times