05. 재귀 알고리즘

05-1. 재귀의 기본

재귀란?

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 함
* 재귀는 병합 정렬과 퀵 정렬(06장), 이진검색트리(10장) 등에 사용됨

순차곱셈 구하기

음이 아닌 정수 n의 순차곱셈 (n!)

• 0! = 1
• n > 0이면 n! = n * n(n-1)!

/* 순차곱셈의 결과를 재귀적으로 구합니다. */
#include <stdio.h> 

/*--- 정수 n의 순차곱셈 값을 반환 ---*/
int factorial(int n)
{
	if (n > 0)
		return n * factorial(n - 1);
	else
		return 1;
}
int main(void)
{
	int x;
	printf("정수를 입력하세요. : ");
	scanf("%d", &x);

	printf("%d의 순차곱셈 값은 %d입니다.\n", x, factorial(x));

	return 0;
}

재귀 호출

재귀 호출은 '함수 자신'을 호출한다고 이해하기보다는 '자기 자신과 똑같은 함수'를 호출한다고 이해하는 것이 자연스러움

직접 재귀와 간접 재귀

직접 재귀(direct) : 자신과 같은 함수를 호출함
factorial 함수는 그 내부에서 factorial 함수를 호출
간접 재귀(indirect) : 다른 함수를 통해 자기 자신과 같은 함수가 호출됨
함수 a가 함수 b를 호출하고, 다시 함수 b가 함수 a를 호출하는 구조

재귀로 정의되는 경우 : 풀어야 할 문제, 계산할 함수, 처리할 데이터 구조

유클리드 호제법

/* 유클리드 호제법에 의해 최대공약수를 구합니다. */
#include <stdio.h> 

/*--- 정수 x, y의 최대공약수를 반환 ---*/
int gcd(int x, int y)
{
	if (y == 0)
		return x;
	else
		return gcd(y, x % y);
}

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

	printf("최대공약수는 %d입니다.\n", gcd(x, y));

	return 0;
}

05-2. 재귀 알고리즘 분석

재귀 알고리즘의 분석

순수하게(genuinely) 재귀적 : 재귀 호출을 여러 회 실행하는 함수

/* 재귀에 대해 깊이 이해하기 위한 재귀 함수 */
#include <stdio.h > 

/*--- 재귀 함수 recur( ) ---*/
void recur(int n)
{
	if (n > 0) {
		recur(n - 1);
		printf("%d\n", n);
		recur(n - 2);
	}
}

int main(void)
{
	int x;
	printf("정수를 입력하세요 : ");
	scanf("%d", &x);
	
	recur(x);

	return 0;
}

하향식 분석(top-down analysis)

가장 위쪽에 위치한 상자의 함수 호출부터 시작해 계단식으로 자세히 조사해 가는 분석 기법
꼭대기(top)부터 분석하면 같은 함수의 호출이 여러 번 나올 수 있기 때문에 '하향식 분석이 반드시 효율적이다'라고 말할 수는 없음

매개변수 n으로 4를 전달하면 recur 함수는 아래 과정을 순서대로 실행
1. recur(3)을 실행합니다.
2. 4를 출력합니다.
3. recur(2)를 실행합니다.

상향식 분석(bottom-up analysis)

아래쪽부터 쌓아 올리며 분석하는 방법

recur(-1) : 아무것도 하지 않음
recur(0) : 아무것도 하지 않음

재귀 알고리즘의 비재귀적 표현

꼬리 재귀의 제거

함수의 꼬리에서 재귀 호출하는 함수 recur(n-2)라는 말은,
'인자로 n-2를 전달하여 recur 함수를 호출한다'는 의미
즉, n의 값을 n-2로 업데이트하고 함수의 시작 지점으로 돌아감

/* 재귀에 대한 이해를 깊게하는 진짜 재귀 함수 */

#include <stdio.h> 

/*--- 함수 recur (맨끝 재귀를 삭제) ---*/
void recur(int n)
{
Top:
	if (n > 0) {
		recur(n - 1);
		printf("%d\n", n);
		n = n - 2;
		goto Top;
	}
}

int main(void)
{
	int x;

	printf("정수를 입력하세요. :");
	scanf("%d", &x);

	recur(x);

	return 0;
}

꼬리 재귀의 경우 쉽게 제거 가능

재귀의 제거

n이 4인 경우 재귀 호출 recur(3)의 처리가 완료되지 않으면 n의 값인 '4'를 저장해야 함
따라서 재귀 호출 recur(n-1)의 경우,
n의 값을 n-1로 업데이트하고 함수의 시작 지점으로 돌아감
* 현재 n의 값을 '잠시' 저장하기 위함 --> stack 이용
recur(n-1)의 처리가 완료된 다음에 n의 값을 출력할 때에는,
저장했던 n을 다시 꺼내 그 값을 출력함

/* 재귀에 대한 이해를 깊게 하는 진짜 재귀 함수 */
#include <stdio.h> 
#include "IntStack.h"

/*--- 함수 recur (재귀를 삭제) ---*/
void recur(int n)
{
	IntStack stk; /* 스택 */
	Initialize(&stk, 100);
Top:
	if (n > 0) {
		Push(&stk, n); /* n 값을 푸시 */
		n = n - 1;
		goto Top;
	}

	if (!IsEmpty(&stk)) {/* 스택이 비어 있지 않으면 */
		Pop(&stk, &n); /* 값을 저장한 n을 팝 */
		printf("%d\n", n);
		n = n - 2;
		goto Top;
	}
	Terminate(&stk);
}

int main(void)
{
	int x;

	printf("정수를 입력하세요. :");
	scanf("%d", &x);

	recur(x);

	return 0;
}

05-3. 하노이의 탑

하노이의 탑

/* 하노이의 탑 */
#include <stdio.h> 

/*--- 원반[1] ~ 원반[no]를 x 기둥에서 y 기둥으로 옮김 ---*/
void move(int no, int x, int y)
{
	if (no > 1)
		move(no - 1, x, 6 - x - y);	/* 그룹을 시작 기둥에서 중간 기둥으로 */
	printf("원반[%d]를 %d 기둥에서 %d 기둥으로 옮김\n", no, x, y);
    	/* 바닥 원반을 목표 기둥으로 */
        
	if (no > 1)
		move(no - 1, 6 - x - y, y); 	/* 그룹을 중간 기둥에서 목표 기둥으로 */
}
int main(void)
{
	int n; 		/* 원반의 개수 */
	printf("하노이의 탑\n원반 개수 : ");
	scanf("%d", &n);

	move(n, 1, 3);

	return 0;
}

05-4. 8퀸 문제

퀸 놓기

체스판은 8*8 = 64칸이므로 64*63*62*61*60*59*58*57 가지의 조합 존재

퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있으므로
각 열에 퀸을 1개만 배치하면 8*8*8*8*8*8*8*8 가지의 조합

퀸은 자신과 같은 행에 있는 다른 퀸을 공격할 수 있으므로 각 행에 퀸을 1개만 배치

가지 뻗기

/* 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열합니다. */
#include <stdio.h> 

int pos[8]; 		/* 각 열에서 퀸의 위치 */

/*--- 각 열의 퀸의 위치를 출력 ---*/
void print(void)
{
	int i;
	for (i = 0; i < 8; i++)
		printf("%2d", pos[i]);
	putchar('\n');
}

/*--- i열에 퀸을 배치 ---*/
void set(int i)
{
	int j;
	for (j = 0; j < 8; j++) {
		pos[i] = j;
		if (i == 7) 		/* 모든 열에 배치되었다면 */
			print();
		else
			set(i + 1);
	}
}
int main(void)
{
	set(0);

	return 0;
}

분할 해결법(divide and conquer)
: 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법

분기 한정법

/* 각 행, 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열합니다. */
#include <stdio.h> 

int flag[8];	/* 각 행에 퀸을 배치했는지 체크하는 배열 */
int pos[8];		/* 각 열에서 퀸의 위치 */

/*--- 각 열에서 퀸의 위치를 출력 ---*/
void print(void)
{
	int i;
	for (i = 0; i < 8; i++)
		printf("%2d", pos[i]);
	putchar('\n');
}

/*--- i열에서 알맞은 위치에 퀸을 배치합니다. ---*/
void set(int i)
{
	int j;
	for (j = 0; j < 8; j++) {
		if (!flag[j]) {		/* j행에 퀸을 배치하지 않았다면 */
			pos[i] = j;
			if (i == 7)		/* 모든 열에 퀸을 배치 */
				print();
			else {
				flag[j] = 1;
				set(i + 1);
				flag[j] = 0;
			}
		}
	}
}

int main(void)
{
	int i;
	for (i = 0; i < 8; i++)
		flag[i] = 0;

	set(0);

	return 0;
}

배열 flag : 같은 행에 중복하여 퀸이 배치되는 것을 방지하기 위한 표시

8퀸 문제를 푸는 프로그램

/* 8퀸 문제 풀이 */
#include <stdio.h> 

int flag_a[8]; 		/* 각 행에 퀸을 배치했는지 체크하는 배열 */
int flag_b[15]; 	/* 대각선 ↙에 퀸을 배치했는지 체크하는 배열 */
int flag_c[15]; 	/* 대각선 ↘에 퀸을 배치했는지 체크하는 배열 */
int pos[8]; 		/* 각 열에서 퀸의 위치 */

/*--- 각 열에서 퀸의 위치를 출력 ---*/
void print(void)
{
	int i;
	for (i = 0; i < 8; i++)
		printf("%2d", pos[i]);
	putchar('\n');
}

/*--- i열에서 알맞은 위치에 퀸을 배치 ---*/
void set(int i)
{
	int j;
	for (j = 0; j < 8; j++) {
		if (!flag_a[j] && !flag_b[i + j] && !flag_c[i - j + 7]) {
			pos[i] = j;
			if (i == 7) /* 모든 열 배치를 마침 */
				print();
			else {
				flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = 1;
				set(i + 1);
				flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = 0;
			}
		}
	}
}

int main(void)
{
	int i;
	for (i = 0; i < 8; i++)
		flag_a[i] = 0;

	for (i = 0; i < 15; i++)
		flag_b[i] = flag_c[i] = 0;

	set(0);

	return 0;
}