유클리드 호제법

알고리즘 문제해결 전략 1권에서 설명한 내용은 이렇다.
유클리드 알고리즘은 두 수 p,q(p>q)의 공약수의 집합은 p-q와 q의 공약수 집합과 같다는 점을 이용한다.

증명

a,b의 공약수 g가 있다고 할때, a=ag, b=bg 로 쓸 수 있다. 그러면 a-b=(a-b)g 이므로 g는 a-b와 b의 공약수이기도 하다. 반대 방향도 같은 방법으로 보일 수 있다.
따라서 a,b의 최대공약수 gcd(a,b)는 항상 a-b와 b의 최대공약수 gcd(a-b,b)와 같다. 이 성질을 이용해 6과 15의 최대공약수를 구해보면..
gcd(6,15) = gcd(9,6) = gcd(3,6) = gcd(3,3) = gcd(0,3)
이 과정을 반복하면 이와 같이 결과적으로 어느 한 수가 0이 된다. 0과 3의 최대공약수는 3이므로, 원래 우리가 구하려 했던 6과 15의 최대공약수도 3이라는 사실을 알 수 있다.

이를 코드로 옮긴다면...

int gcd(int a, int b){
    if(a>b) swap(a,b);
    if(b==0) return a;
    return gcd(a-b, b);
}

이 코드는 깔금하지만 아직 더 최적화할 수 있는 구석이 남아있다.
gcd(1024,6)을 호출했다고하면 아마 다음과 같이 재귀 호출이 이루어질 것이다.
gcd(1024,6)=gcd(1018,6)=gcd(1012,6)=gcd(1006,6)=...
이와 같은 재귀 호출은 gcd(4,6)이 호출될 때까지 계속될 것이다.
gcd(1024,6)에서 gcd(4,6)까지 앞으로 빠르게 돌리는 방법은 p에서 q를 빼는 대신 p를 q로 나눈 나머지를 취하면 된다. 아래 코드는 이와 같은 새로운 gcd()의 구현을 보여준다.
a < b 일 때에 대한 처리를 따로 하지 않은 점을 눈여겨 보자. a < b인 입력이 들어올 경우 a % b = a 이므로, 다음 재귀 호출은 자동으로 gcd(b,a)가 되기 때문이다.

최적화 코드

public static int gcd(int a, int b) {
   return b == 0 ? a : gcd(b, a%b);
}