SICP問題1.20

今回は最大公約数に関する問題。

↓は最大公約数を求める手続き。

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

でこの手続きを使って(gcd 206 40)を正規順序、作用的順序で評価していったら
remainderは何回実行されるか。

正規順序

(gcd 206 40) 0
(if (= 40 0) 206 (gcd 40 (remainder 206 40)))0
(if (= 40 0) 206 (if (= 6 0) 40 (gcd 6 (remainder 40 6)))) 1
(if (= 40 0) 206 (if (= 6 0) 40 (if (= 4 0) 6 (gcd 4 (remainder 6 4))))) 2
(if (= 40 0) 206 (if (= 6 0) 40 
                 (if (= 4 0) 6 (if (= 2 0) 4 (gcd 2 (remainder 4 )))))) 3
4

で、4回*1

作用的順序

(gcd 206 40) 0
(gcd 40 
     (remainder 206 40))) 0

(gcd (remainder 206 40) 
     (remainder 40 (remainder 206 40)))) 1

(gcd (remainder 40 (remainder 206 40)) 
     (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 3

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

(remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 14
18

で、１８回。

*1:行末の数字はそこまでの実行回数