이 글에서는 재귀(recursion)를 활용하여 두 수의 최대공약수(G.C.D, Greatest Common Divisor)를 구하는 자바 프로그램 작성 방법을 알아보겠습니다.
재귀 함수란 특정 조건이 만족될 때까지 스스로를 반복해서 호출하는 함수를 의미합니다. 두 수의 최대공약수란 두 수를 모두 나누어 떨어지게 하는 수 중 가장 큰 수를 말합니다.
재귀(Recursion)란?
재귀는 항목들을 자기 유사(self-similar)한 방식으로 반복하는 과정입니다. 프로그래밍 언어에서 어떤 함수가 자기 자신을 다시 호출할 수 있다면, 이를 해당 함수의 재귀 호출(recursive call)이라고 부릅니다.
대부분의 프로그래밍 언어는 스택(stack)을 이용해 재귀를 구현합니다. 일반적으로 한 함수(호출자)가 다른 함수 또는 자기 자신(피호출자)을 호출하면, 호출자는 실행 제어권을 피호출자에게 넘기며, 이 과정에서 데이터도 함께 전달될 수 있습니다.
입력 및 출력 예시
입력
두 개의 숫자 입력: 24와 36
출력
24와 36의 G.C.D는 12입니다.
알고리즘
1단계 - 시작 2단계 - my_input_1, my_input_2, my_result 세 개의 변수를 선언 3단계 - 사용자로부터 필요한 값을 입력받거나 값을 직접 정의 4단계 - 두 개의 정수를 매개변수로 받아 'my_input_2' 값과 'my_input_1' % 'my_input_2' 값을 반환하는 재귀 함수 'CommonFactor'를 정의 5단계 - 'my_input_2'가 0보다 클 때까지 함수를 재귀적으로 호출하고 결과를 저장 6단계 - 결과 출력 7단계 - 종료
예제 1: 사용자로부터 입력받는 경우
다음 예제는 사용자가 직접 두 수를 입력하는 방식입니다. 온라인 코딩 도구에서 직접 실행해 볼 수 있습니다.
import java.util.Scanner;
public class GCD {
public static void main(String[] args) {
int my_input_1, my_input_2, my_result;
System.out.println("필요한 패키지를 가져왔습니다");
Scanner my_scanner = new Scanner(System.in);
System.out.println("Scanner 객체가 생성되었습니다 ");
System.out.print("첫 번째 숫자를 입력하세요 : ");
my_input_1 = my_scanner.nextInt();
System.out.print("두 번째 숫자를 입력하세요 : ");
my_input_2 = my_scanner.nextInt();
my_result = CommonFactor(my_input_1, my_input_2);
System.out.printf("%d와 %d의 G.C.D는 %d입니다.", my_input_1, my_input_2, my_result);
}
public static int CommonFactor(int my_input_1, int my_input_2){
if (my_input_2 != 0)
return CommonFactor(my_input_2, my_input_1 % my_input_2);
else
return my_input_1;
}
}
실행 결과
필요한 패키지를 가져왔습니다 Scanner 객체가 생성되었습니다 첫 번째 숫자를 입력하세요 : 24 두 번째 숫자를 입력하세요 : 36 24와 36의 G.C.D는 12입니다.
예제 2: 값이 미리 정의된 경우
다음 예제는 두 정수가 코드 내에 미리 정의되어 있으며, 그 값을 콘솔에 바로 출력합니다.
public class GCD {
public static void main(String[] args) {
int my_input_1, my_input_2, my_result;
my_input_1 = 24;
my_input_2 = 36;
System.out.println("정의된 두 숫자는 " +my_input_1 +"과 " +my_input_2 +"입니다");
my_result = CommonFactor(my_input_1, my_input_2);
System.out.printf("%d와 %d의 G.C.D는 %d입니다.", my_input_1, my_input_2, my_result);
}
public static int CommonFactor(int my_input_1, int my_input_2){
if (my_input_2 != 0)
return CommonFactor(my_input_2, my_input_1 % my_input_2);
else
return my_input_1;
}
}
실행 결과
정의된 두 숫자는 24과 36입니다 24와 36의 G.C.D는 12입니다.
정리
이처럼 유클리드 호제법(Euclidean algorithm)을 기반으로 한 재귀 함수를 사용하면, 나머지 연산(%)을 반복 적용하여 두 수의 최대공약수를 간결하고 효율적으로 구할 수 있습니다. 재귀 호출은 두 번째 인자가 0이 되는 시점에 종료되며, 그때의 첫 번째 인자가 곧 최대공약수가 됩니다.