2. 재귀

2-1. 함수의 재귀적 호출의 이해

 

* 재귀 함수의 기본적인 이해

재귀 함수: 함수 내에서 자기 자신을 다시 호출하는 함수

재귀 함수의 구성: 재귀의 탈출 조건, 재귀의 탈출, 함수의 재귀적 호출

void Recursive(int num)
{
	if (num <= 0) // 재귀의 탈출 조건
		return; // 재귀의 탈출
	printf("Recursive call! %d\n", num);
	Recursive(num - 1); // 함수의 재귀적 호출
}

 

* 재귀 함수의 예시

int Factorial(int n) {
	if (n == 0)
		return 1;
	else
		return n * Factorial(n - 1);
}

 

2-2. 재귀의 활용

 

* 피보나치 수열

int Fibonacci(int n) {
	if (n == 1)
		return 0;
	else if (n == 2)
		return 1;
	else
		return Fibonacci(n - 1) + Fibonacci(n - 2);
}

 

* 이진 탐색 알고리즘의 재귀적 구현

int BinarySearchRecursion(int arr[], int first, int last, int target) {
	int mid;
	if (first > last)
		return -1; // 탐색의 실패를 의미하는 반환값
	mid = (first + last) / 2;  // 탐색 대상의 중앙을 찾는다.
	if (arr[mid] == target)
		return mid; // 탐색된 타겟의 인덱스 값 반환
	else if (target < arr[mid])
		return BinarySearchRecursion(arr, first, mid - 1, target);
	else
		return BinarySearchRecursion(arr, mid + 1, last, target);
}

 

2-3. 하노이 타워

 

* 하노이 타워 문제의 이해

세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 초기에 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓으면 문제가 해결된다.

1. 한 번에 한 개의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

3단 하노이 타워의 해결 과정은 다음과 같다.

3단 하노이 타워의 해결 과정

그렇다면 n단 하노이 타워는 어떻게 해결할 수 있을까?

 

* 하노이 타워 문제의 해결

하노이 타워 문제는 재귀적으로 해결이 가능하다.

1. 작은 원판 n - 1 개를 A 막대에서 B 막대로 이동

2. 제일 큰 원판을 A 막대에서 C 막대로 이동

3. 작은 원판 n - 1 개를 B 막대에서 C 막대로 이동

 

다음 해결 과정을 재귀 함수로 표현하면 다음과 같다.

void HanoiTowerMove(int num, char from, char by, char to) {
	if (num == 1) // 이동할 원판의 수가 1개라면
		printf("원판1을 %c에서 %c로 이동\n", from, to);
	else {
		HanoiTowerMove(num - 1, from, to, by); // 3단계 중 1단계
		printf("원판%d을(를) %c에서 %c로 이동\n", num, from, to); // 3단계 중 2단계
		HanoiTowerMove(num - 1, by, from, to); // 3단계 중 3단계
	}
}