유클리드 호제법을 리슾으로 표현해보자


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


만일 리슾 인터프리터가 normal order를 사용한다면?

(노말 오더는 기본 연산자(여기서는 %)가 올 때까지 함수의 적용을 미룬다)

206과 40의 최대공약수를 위에서 정의한 gcd로 구해본다


(gcd 206 40) (if (= 40 0) 206 (gcd 40 (% 206 40))) (gcd 40 (% 206 40)) (if (= (% 206 40) 0) 40 (gcd (% 206 40) (% 40 (% 206 40)))) (if (= 6 0) ; <-------------- %: 1 40 (gcd (% 206 40) (% 40 (% 206 40)))) (gcd (% 206 40) (% 40 (% 206 40))) (if (= (% 40 (% 206 40)) 0) (% 206 40) (gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))) (if (= (% 40 6) 0) ; <-------------- %: 2 (% 206 40) (gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))) (if (= 4 0) ; <-------------- %: 3 (% 206 40) (gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))) (gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) (if (= (% (% 206 40) (% 40 (% 206 40))) 0) (% 40 (% 206 40)) (gcd (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))) (if (= (% (% 206 40) (% 40 6)) 0) ; 4 (% 40 (% 206 40)) (gcd (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))) (if (= (% (% 206 40) 4) 0) ; 5 (% 40 (% 206 40)) (gcd (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))) (if (= (% 6 4) 0) ; 6 (% 40 (% 206 40)) (gcd (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))) (if (= 2 0) ; 7 (% 40 (% 206 40)) (gcd (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))) (gcd (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))) (if (= (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) 0) (% (% 206 40) (% 40 (% 206 40))) (gcd (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) (% (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))) (if (= (% (% 40 (% 206 40)) (% (% 206 40) (% 40 6))) 0) ; 8 (% (% 206 40) (% 40 (% 206 40))) (gcd (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) (% (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))) (if (= (% (% 40 (% 206 40)) (% (% 206 40) 4)) 0) ; 9 (% (% 206 40) (% 40 (% 206 40))) (gcd (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) (% (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))) (if (= (% (% 40 (% 206 40)) (% 6 4)) 0) ; 10 (% (% 206 40) (% 40 (% 206 40))) (gcd (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) (% (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))) (if (= (% (% 40 (% 206 40)) 2) 0) ; 11 (% (% 206 40) (% 40 (% 206 40))) (gcd (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) (% (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))) (if (= (% (% 40 6) 2) 0) ; 12 (% (% 206 40) (% 40 (% 206 40))) (gcd (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) (% (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))) (if (= (% 4 2) 0) ; 13 (% (% 206 40) (% 40 (% 206 40))) (gcd (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) (% (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))) (if (= 0 0) ; 14 (% (% 206 40) (% 40 (% 206 40))) (gcd (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))) (% (% (% 206 40) (% 40 (% 206 40))) (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))) (% (% 206 40) (% 40 (% 206 40))) (% (% 206 40) (% 40 6)) ;15 (% (% 206 40) 4) ;16 (% 6 4) ;17 2 ; use remainder(%) 18 times!


그만 정신을 잃고 말았습니다...