문제 정의
C 프로그래밍 언어에서 재귀 함수(recursive function)를 활용하여 주어진 두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 프로그램을 작성하는 것이 이번 글의 목표입니다.
해결 접근 방법
최대공약수는 유클리드 호제법(Euclidean algorithm)을 기반으로 구할 수 있습니다. 두 수 중 큰 수를 작은 수로 나눈 나머지를 구하고, 이 과정을 나머지가 0이 될 때까지 반복하면 그 시점의 값이 곧 최대공약수가 됩니다. 이 반복 과정을 함수가 자기 자신을 호출하는 재귀 방식으로 구현하면 코드가 간결하고 직관적으로 완성됩니다.
알고리즘
재귀 함수를 사용해 두 수의 최대공약수를 구하는 알고리즘은 다음과 같습니다.
1단계 − 재귀 함수를 정의합니다.
2단계 − 두 개의 정수 a와 b를 입력받습니다.
3단계 − 재귀 함수를 호출합니다. 함수 내부의 동작 흐름은 다음과 같습니다.
a. 만약 i > j 라면, b. 매개변수 i, j를 서로 바꾸어 함수를 다시 호출합니다. c. 만약 j == 0 이라면, d. i 값을 반환합니다. e. 그렇지 않으면 매개변수 j, i%j 로 함수를 재귀 호출합니다.
순서도(플로우차트)
아래 순서도는 재귀 함수를 이용해 최대공약수를 구하는 알고리즘의 전체적인 처리 흐름을 보여줍니다.
예제 코드
다음은 재귀 함수를 사용하여 주어진 두 수의 최대공약수(GCD)를 구하는 C 프로그램입니다.
#include<stdio.h>
#include<math.h>
unsigned int GCD(unsigned i, unsigned j);
int main(){
int a,b;
printf("Enter the two integers: \n");
scanf("%d%d",&a,&b);
printf("GCD of %d and %d is %d\n",a,b,GCD(a,b));
return 0;
}
/* 재귀 함수 */
unsigned int GCD(unsigned i, unsigned j){
if(j>i)
return GCD(j,i);
if(j==0)
return i;
else
return GCD(j,i%j);
}코드 설명
프로그램이 실행되면 먼저 사용자로부터 두 개의 정수를 입력받습니다. 이후 GCD() 함수가 호출되는데, 이 함수는 세 가지 경우를 처리합니다.
- 첫 번째 매개변수보다 두 번째 매개변수가 더 크면, 두 인자의 순서를 바꾸어 자기 자신을 다시 호출합니다.
- 두 번째 값이 0이 되면 첫 번째 값이 곧 최대공약수이므로 이를 반환하고 재귀를 종료합니다.
- 그 외의 경우에는 두 번째 값과 나머지 연산 결과(i%j)를 인자로 넘겨 재귀 호출을 계속 진행합니다.
실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 결과를 확인할 수 있습니다.
Enter the two integers: 4 8 GCD of 4 and 8 is 4
입력한 두 수 4와 8의 최대공약수가 4로 올바르게 출력되는 것을 볼 수 있습니다. 이처럼 유클리드 호제법을 재귀 함수로 구현하면 적은 코드량으로도 효율적으로 최대공약수를 계산할 수 있습니다.