재귀를 사용한 최대공약수 (GCD) 구하기

소개

수학에서 두 숫자의 최대 공약수 (GCD, Greatest Common Divisor) 는 두 숫자를 나누어 떨어지게 하는 가장 큰 양의 정수로 일반적으로 정의됩니다. 이 Lab 에서는 재귀를 사용하여 두 숫자의 GCD 를 구하는 C 프로그램을 작성하는 방법을 배웁니다.

참고: 코딩을 연습하고 gcc 를 사용하여 컴파일하고 실행하는 방법을 배우려면 직접 ~/project/main.c 파일을 생성해야 합니다.

cd ~/project
## create main.c
touch main.c
## compile main.c
gcc main.c -o main
## run main
./main

입력 숫자 읽기

먼저, GCD 를 구하기 위해 사용자로부터 두 개의 정수 입력 숫자를 받아야 합니다. scanf() 함수를 사용하여 입력을 읽습니다.

#include<stdio.h>

int main()
{
    int a, b;
    printf("GCD 를 구할 두 숫자를 입력하세요: \n");
    scanf("%d%d", &a, &b);
    // rest of the code
    return 0;
}

GCD 를 구하는 재귀 함수 정의

두 입력 숫자의 GCD 를 구하기 위해 재귀 함수를 사용합니다. 재귀 함수는 두 개의 정수 매개변수를 갖습니다. 이 함수는 두 숫자가 동일한 값을 가질 때까지 계속해서 자신을 호출하고 해당 값을 GCD 로 반환합니다.

int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

메인 함수에서 재귀 함수 호출

이 단계에서는 두 입력 숫자 (a 와 b) 를 사용하여 재귀 함수를 호출합니다. 재귀 함수의 반환 값은 정수 변수 (gcd) 에 저장됩니다.

int gcd = find_gcd(a, b);
printf("GCD of %d and %d is: %d\n", a, b, gcd);

전체 예제 코드

#include <stdio.h>

// 재귀 함수 선언
int find_gcd(int, int);

int main()
{
    int a, b, gcd;
    printf("GCD 를 구할 두 숫자를 입력하세요: \n");
    scanf("%d%d", &a, &b);
    gcd = find_gcd(a, b);
    printf("GCD of %d and %d is: %d\n", a, b, gcd);
    return 0;
}

// 함수 정의
int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

요약

이 랩에서는 재귀를 사용하여 두 숫자의 최대공약수 (GCD, Greatest Common Divisor) 를 구하는 C 프로그램을 작성하는 방법을 배웠습니다. 재귀 함수를 사용하여 기본 사례 (base case) 에 도달할 때까지 수정된 입력 매개변수를 사용하여 함수 자체를 호출함으로써 GCD 를 계산했습니다. 이 프로그램은 두 숫자의 GCD 계산이 필요한 수학 문제를 해결하는 데 사용할 수 있습니다.