SW 마에스트로 멘토님의 추천으로 SICP 를 공부중이다. 책에서 사용하는 언어는 Scheme이라고 하는 Lisp의 dialect인데, 지금까지 배운 언어들과는 꽤 다르지만 재밌는 언어다.
연습문제 1.20
유클리드 호제법 알고리즘을 통해 인자 먼저 계산법과 정의대로 계산법을 비교하는 문제이다.
유클리드 호제법 알고리즘 자체는 무척 간단하다.
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
- 인자 먼저 계산법
인자 먼저 계산법을 사용해 (gcd 206 40) 의 계산 프로세스를 적어 보자
(gcd 206 40)
(gcd 40 (remainder 206 40))
; 인자를 먼저 계산하므로
(gcd 40 6)
(gcd 6 (remainder 40 6))
(gcd 6 4)
(gcd 4 (remainder 6 4))
(gcd 4 2)
(gcd 2 (remainder 4 2))
(gcd 2 0)
2
정의대로 계산법을 사용하면 다음과 같은 프로세스가 나온다.
(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
(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)))))
; 위 gcd 에서 b == 0 이므로
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
(remainder (remainder 206 40) (remainder 40 6))
(remainder (remainder 206 40) 4)
(remainder 6 4)
2
정의대로 계산하는 방법이 같은 계산을 여러번 반복하기 때문에 확실히 비효율적인 것을 알 수 있다.