유클리드 호제법 ( Euclidean algorithm )

이름은 엄청 어려워보이는데,
사실 그냥 재귀함수를 통해 최대공약수를 구하는 알고리즘이다.

코드는 굉장히 간단하다.

	static int gcd(int a, int b) {
        if ( b == 0 ) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

a = 15 , b = 10 이라고 가정한 뒤
위 코드를 간단한 슈도코드로 디버깅해보겠다.

1. 
a = 15, b = 10,
b != 0, then gcd(10 , 15 % 10) => gcd(10, 5)

2. 
a = 10, b = 5,
b != 0 , then gcd(5, 10 % 5) => gcd(5, 0)

3.
a = 5, b = 0,
b == 0, then return a => 5 return, 

정답) 15와 10의 최대 공약수는 5다.