[Algorithm] 유클리드 호제법(유클리드 알고리즘) _ 재귀 함수

 

재귀 함수란 자기 자신을 재 호출하는 함수를 말한다.

 

 

예를 들어 코드를 보자

 

package algorithm;

public class recursive_fun {
	public static void main(String[] args) {
		recursive_function();
	}
	
	public static String recursive_function() {
		System.out.println("재귀 함수 호출");
		return recursive_function();
	}
}

 

 

위와 같은 코드가 있다면

 

recursive_function() 함수를 호출한 뒤 "재귀 함수 호출"을 print 하고

 

다시 recursive_function() 함수를 재호출하여 "재귀 함수 호출"을 print 하는 방식을 반복한다.

 

 

 

결과 : 무한 print

 

 

그 결과 "재귀 함수 호출"을 무한대로 출력하게 된다.

 

 

그러므로 재귀함수를 사용할 때에는 종료 조건을 명시해줘야한다.

 

 

 

 

---

 

 

아무튼 이 재귀함수를 이용하여 유클리드 호제법을 구현해볼 수 있다.

 

 

유클리드 알고리즘은 2개의 수의 최대공약수를 구하는 알고리즘이다.

 

 

 

 

 

 

 

유클리드 알고리즘에서 중요한 점은

 

 

A > B 일 때

 

A ÷ B 의 나머지 값이 R이라면

 

A와 B의 최대공약수는 B와 R의 최대공약수와 같다는 점이다.

 

 

 

 

 

예를 들어보자.

 

 

192와 162의 최대공약수는 6이다.

 

 

 

 

192와 162의 최대공약수는 6이다.

 

 

 

 

 

그리고 192 % 162 = 30이므로

 

 

162와 30의 최대공약수도 6이다.

 

 

 

 

162와 30의 최대공약수를 구해보면 마찬가지로 6이 나온다.

 

 

 

 

 

162 % 30 = 12 이므로

 

 

30과 12의 최대공약수도 6이다.

 

 

 

 

 

30과 12의 최대공약수를 구해보면 마찬가지로 6이다.

 

 

 

 

30 % 12 = 6이므로

 

 

12와 6의 최대공약수도 6이다.

 

 

 

 

12와 6의 최대공약수 또한 6이 된다.

 

 

그리고 12 % 6 = 0이므로 끝맺으면 된다.

 

 

 

이렇듯 같은 연산을 반복하므로 이는 재귀 함수로 표현할 수 있다.

 

 

 

 

 

 

코드

package algorithm;

public class recursive_fun {
	public static void main(String[] args) {
		System.out.println(recursive_function(192, 162));
	}
	
	public static int recursive_function(int a, int b) {
		if(a % b == 0)
			return b;
		else {
			return recursive_function(b, a % b);
		}
	}

}

 

 

 

이를 실행해보면 당연히 6이 나온다.

 

 

 

 

이렇게 유클리드 알고리즘을 재귀 함수로 표현할 수 있다.