재귀 알고리즘 실습 - 최대공약수 구하기

✅해결 과정

1. x가 큰 값, y가 작은 값이라고 가정

2. x%y == 0 만족하면 최대 공약수는 x임 --종결 조건

3. x%y != 0 이면 작은 값(y)를 다시 x%y로 나누어 줌 (이 과정에서 y가 큰 값, x%y가 작은 값으로 바뀜)

4. 나누어 떨어질 때까지 과정 재귀적 반복

 

최대공약수 구하는 함수를 gcd(x, y)라 하면

3번을 위해 gcd(y, x%y) return하게 함(y를 큰 쪽(왼 쪽), x%y를 작은 쪽(오른 쪽)으로) 

 

🔺어떤 두 수가 와도 작은 값이 오른쪽 파라미터쪽이 됨 (ex.gcd(6, 10)-->gcd(10, 6))

 

✅코드

/*최대공약수 구하기*/
#include <stdio.h>

int gcd(int x, int y)		
{
  if(y==0) return x;		
  return gcd(y, x % y);
}
int main(void) {
  int x, y;
  printf("두 정수를 입력: ");
  scanf("%d %d", &x, &y);
  printf("두 수의 최대공약수 : %d\n",gcd(x, y));
  return 0;
}