[c언어] 최대공약수 구하기 (재귀함수)

두 정수의 최대공약수를 구하는 함수를 재귀함수를 이용하여 작성한다.

 

*논리

큰수 x와 작은 수 y를 매개변수로 받아서 y가 0이면 x를 반환하고, 

0이 아니면 작은 수 y와 (큰수 % 작은수)를 매개변수로 자기 자신 함수를 재귀호출한다.

 

#include <stdio.h>

int gcd(int x, int y)
{
    if (y == 0)
        return x;
    else
        return gcd(y, (x % y));
}

int main(void)
{
    int a, b, big, small;

    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);

    if (a < b) {
        big = b;
        small = a;
    }

    else {
        big = a;
        small = b;
    }

    printf("%d와 %d의 최대공약수는 %d\n", a, b, gcd(big, small));
}

 

결과