[알유] 재귀 함수 - 2

유클리드 호제법이란?

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 호제법은 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 말한다.

알고리즘 순서는 아래와 같다.

1. 입력으로 두 수 m,n(m > n)이 입력된다.
2. n이 0이라면 m을 출력하고 알고리즘을 종료한다.
3. m이 n으로 나누어 떨어지면 n을 출력하고 알고리즘을 종료한다.
4. 그렇지 않으면 m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아간다.

예시

1. 22는 8로 나누어 떨어지지 않기 떄문에 22를 8로 나눈 나머지를 구한다. -> 6
2. 8은 6으로 나누어떨어지지 않기 때문에 8를 6으로 나눈 나머지를 구한다. -> 2
3. 6은 2와 나누어떨어진다.

---

코드

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

---

• 참고 : Do it 자료구조와 함께 배우는 알고리즘 입문 자바 편
• 위키백과