[자료구조] 3. 재귀의 활용

 

재귀함수란?

 

1) 팩토리얼 계산

2) 거듭제곱값 계산

3) 피보나치 수열

4) 이진 탐색 알고리즘

5) 하노이 타워

 

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

 

=> 동일한 패턴의 작업을 반복해서 진행

 * 재귀의 탈출 조건이 반드시 있어야 한다.

 

---

1) 팩토리얼 계산

 

[재귀함수 탈출 조건] : 0!을 구함

 

#include <stdio.h>


// 팩토리얼 함수
int Factorial(int n) {
	if (n == 0)
	    return 1;
	else
	    return n* Factorial(n - 1);
}

int main(void) {

	int n = 5;

	printf("%d! = %d", n, Factorial(n));
	return 0;
}

---

2) 거듭제곱값 계산

 

[재귀함수 탈출 조건] : 0제곱 값을 구함

 

#include <stdio.h>

// x의 n제곱 값을 구하는 함수 

int Power(int x, int n) {

	if (n == 0)
		return 1;
	else if ((n % 2 == 0))  // n이 짝수인 경우
		return Power(x * x, n / 2);
	else                    // n이 홀수인 경우
		return x * Power(x * x, (n - 1) / 2);
}

int main(void) {

	int x = 2;
	int n = 7;

	printf("%d의 %d제곱 값 : %d", x, n, Power(x, n));
}

---

3) 피보나치 수열

 

[재귀함수 탈출 조건] : 피보나치 수열의 첫 번째, 두 번째 값을 구함

 

#include <stdio.h>

// 피보나치 수열의 n번째 값을 구하는 함수
int Fibo(int n) {
	if (n == 1)
		return 0;
	else if (n == 2)
		return 1;
	else
		return Fibo(n - 1) + Fibo(n - 2);   // * 함수 호출 순서 - '+'연산자 왼편에 있는 Fibo 함수 호출이 완료되어야 오른편의 Fibo 함수 호출이 진행 된다.
}

int main(void) {

	int k = 10;

	// 피보나치 수열 k번째 항까지 출력
	for (int i = 1; i <= k; i++)
		printf("%d  ", Fibo(i));

	return 0;
}

---

4) 이진 탐색 알고리즘

 

[이진 탐색 알고리즘의 패턴] 

탐색 범위의 중앙에 목표 값이 저장되었는지 확인 → 해당 위치에 목표 값이 없다면 탐색 범위를 반으로 줄여서 다시 탐색

 

[재귀함수 탈출 조건] 

   - 탐색 성공 (목표 값이 존재)

   - 탐색 실패(목표 값이 존재하지 않음) - 탐색 범위의 시작 위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우

 

#include <stdio.h>

// 이진 탐색 알고리즘으로 탐색 대상에 목표 값이 존재하는 탐색하고 그 위치를 구하는 함수
int BinarySearch(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 BinarySearch(arr, first, mid - 1, target);
	else
		return BinarySearch(arr, mid + 1, last, target);
}

int main(void) {

	int arr[] = { 1, 3, 5, 7, 9, 11, 13 };
	int idx;   //목표 값이 위치한 인덱스
	int n = 7;     //목표 값

	idx = BinarySearch(arr, 0, sizeof(arr) / sizeof(int) - 1, n);

	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인텍스 : %d \n", idx);

	return 0;
}

 

 

cf ) 반복문을 이용하여 구현한 이진 탐색 알고리즘

 

#include <stdio.h>

// 이진 탐색 알고리즘으로 탐색 대상에 목표 값이 존재하는 탐색하고 그 위치를 구하는 함수
int BinarySearch(int arr[], int len, int target) {

	int first = 0;    // 탐색 대상의 시작 인덱스
	int last = len - 1;    // 탐색 대상의 마지막 인덱스
	int mid;

	while (first <= last) {
		mid = (first + last) / 2;

		if (target == arr[mid])   // 탐색 성공
			return mid;
		else {
			if (target < arr[mid])
				last = mid - 1;
			else
				first = mid + 1;
		}

		return -1;    // 탐색 실패
	}
}

int main(void) {

	int arr[] = { 1, 3, 5, 7, 9, 11, 13 };
	int idx;   //목표 값이 위치한 인덱스
	int n = 7;     //목표 값

	idx = BinarySearch(arr, sizeof(arr) / sizeof(int), n);

	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	return 0;
}

---

5) 하노이 타워

 

[하노이 타워 반복 패턴]

 

1단계 : 작은 원반 n-1개(맨 아래 원반을 제외한 나머지 원반)를 A에서 B로 이동 

2단계 : 큰 원반 1개(맨 아래 원반)를 A에서 C로 이동

3단계 : 작은 원반 n-1개(1단계에서 옮겨진 원반)를 B에서 C로 이동

 

 

[재귀함수 탈출 조건] : 이동해야 할 원반의 수가 1개인 경우

 

#include <stdio.h>

// 하노이타워 구현 함수 : from에 꽂혀있는 num개의 원반을 by를 거쳐 to로 이동
void HanoiTowerMove(int num, char from, char by, char to) {

	if (num == 1) {
		printf("원반1을 %c에서 %c로 이동 \n", from, to);
	}
	else {
		HanoiTowerMove(num - 1, from, to, by);
		printf("원반%d를 %c에서 %c로 이동 \n", num, from, to);
		HanoiTowerMove(num - 1, by, from, to);
	}
}

int main(void) {

	// 막대 A의 원반 3개를 막대 B를 경유하여 막대C로 옮기기
	HanoiTowerMove(3, 'A', 'B', 'C');

	return 0;
}