재귀 알고리즘 / 순차곱셈 구하기, 유클리드 호제법 구현

재귀란?

 

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.
프로그래밍에서 재귀를 효과적으로 잘 사용하면 이런 정의뿐만 아니라 프로그램도 간결하게 할 수 있다.

재귀를통해 이루어진 송강호의 뎀프시롤

 

순차곱셈 구하기

 

재귀의 대표적인 예로 음이 아닌 정수의 순차곱셈(factorial)을 구하는 것이 있다.

음이 아닌 정수 n의 순차곱셈 (n!)은 아래처럼 재귀적으로 정의 할 수 있다.

 

0! = 1
n > 0이면 n! = n x (n-1)!

 

코드를 통해 알아보도록 하자

 

#include<stdio.h>

int factorial(int n)
{
	if (n > 0)
		return n * factorial(n - 1);
	else
		return 1;
}

int main(void)
{
	int x;
	printf("정수를 입력하세요: ");
	scanf_s("%d", &x);
	printf("%d의 순차곱셈 값은 %d 입니다.\n", x, factorial(x));


	return 0;
}

 

음이 아닌 정수를 넣었을때 0보다 크다면 재귀적으로 n*factorial(n-1)을 리턴하게 한다.

아니라면 1을 리턴한다.

 

3!을 구하기위해 팩토리얼 함수를 이용했다고 생각해보자.

 

- 3은 0보다 크기 때문에 n * 팩토리얼함수(2) 가 된다. 팩토리얼함수(2)를 구하기위해 팩토리얼 함수를 호출. (1번)

- 2는 0보다 크기 때문에 n * 팩토리얼함수(1) 이 된다. 팩토리얼함수(1)을 구하기위해 팩토리얼 함수를 호출. (2번)

- 1는 0보다 크기 때문에 n * 팩토리얼함수(0) 이 된다. 팩토리얼함수(0)을 구하기위해 팩토리얼 함수를 호출. (3번)

 

- 0은 조건에 부합하지 않기때문에 1을 리턴한다. 

- 1을 리턴받은 3번은 1 * (리턴값 1) 이기 때문에 1을 (2번)에 리턴해준다.

- 1을 리턴받은 2번은 2 * (리턴값 1) 이기 때문에 2를 (1번)에 리턴해준다.

- 2를 리턴받은 1번은 3 * (리턴값 2) 이기 때문에 최종값으로 6을 리턴한다.

 

직접 재귀와 간접 재귀

 

 직접재귀

위 팩토리얼 함수와 같이 자신과 같은 함수를 호출하면 직접 재귀

간접 재귀

함수 a가 함수 b를 호출하고, 다시 함수 b가 함수 a를 호출하는 구조로 이루어지는 재귀

 

 

유클리드 호제법 구현

 

두 정수의 최대 공약수를 구하기위해 유클리드 호제법을 사용하는데 

 

정수1과 정수2의 최대 공약수를 구하기위해 정수1을 정수2로 나눈다고 한다면,

정수2를 정수1과 정수2를 나눈 나머지로 나눠주면 된다.

이 나머지가 0이 될때까지 나눠야 하기때문에 재귀를 실습해보는데 적합하다.

 

ex. 1980과 168의 최대공약수를 구해야 한다면

 

1980  = 168 * 11 + 132   // 1980을 168로 나누면 몫이 11이고 나머지가 132이다.

168 = 132*1+36  // 나눈 값인 168을 위의 계산에서 나온 나머지인 132로 나누어준다.

132 = 36 * 3 +24  // 반복

36 = 24 * 1 + 12 

24 = 12 * 2 + 0 //나머지가 0이 될때

 

-> 1980과 168의 최대공약수는 12가 된다.

 

 

 

코드로 구현해보자.

 

#include<stdio.h>

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

int main(void)
{
	int x, y;
	puts("두 정수의 최대 공약수를 구합니다.");
	printf("정수를 입력하세요 : ");
	scanf_s("%d", &x);
	printf("정수를 입력하세요 : ");
	scanf_s("%d", &y);
	printf("최대공약수는 %d 입니다.\n", Euclidean(x, y));


	return 0;
}

 

만약 x를 나눌 값인 y가 0이라면 x를 리턴하고

아니라면 함수를 호출해서 x%y를 한 값이 0이 리턴될때까지 재귀한다.

 

함수를 리턴했을때는 함수의 매개변수 x의 값으로 현재 y의 값이 들어가기 때문에

(위의 설명으로 얘기하자면 정수2가 들어가는것)

 

함수가 새로 호출되고 나눈 나머지가 0이라면 x가 리턴이 되어 최대공약수가 리턴이 되는 것이다.

 

결과가 잘 나오는것을 볼 수 있다.