이 포스팅은 윤성우님의 열혈 자료구조를 기반으로 합니다.
2-1 함수의 재귀적 호출의 이해
재귀 함수란 함수 내에서 자기 자신을 다시 호출하는 함수를 말하며 동작 과정은 다음과 같다.
먼저 다음의 재귀함수 코드를 보자.
|
1
2
3
4
|
void Recursive(void) {
printf("Recursive call! \n");
Recursive();
}
|
cs |
이를 그림으로 표현하면 다음과 같다.
Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면, Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 된다. 재귀 함수의 중요한 점은 바로 탈출 조건을 설정해야 한다는 것이다.
위의 코드의 경우 탈출 조건이 없으므로 무한 호출이 된다. 다음의 코드에서는 탈출 조건을 설정하여 3번 출력이 되는것을 확인할 수 있다.
<RecursiveFunc.c>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <stdio.h>
void Recursive(int num) {
if (num <= 0) // 탈출 조건
return;
printf("Recursive call! %d \n", num);
Recursive(num - 1);
}
int main(void) {
Recursive(3);
return 0;
}
|
cs |
<실행결과>
재귀함수의 예시로 팩토리얼 함수를 들 수 있다. 먼저 팩토리얼의 수식을 쓰면 다음과 같다.
이를 코드적인 관점에서 생각해보면 n이 1인 경우는 1을 반환하고 그 이외의 경우는 n-1을 반환하면 되는 것이다.
코드로 작성하면 다음과 같다.
<RecursiveFactorial.c>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <stdio.h>
int Factorial(int num) {
if (num == 0) // 탈출 조건
return 1;
return num * Factorial(num - 1);
}
int main(void) {
printf("1! = %d\n", Factorial(1));
printf("2! = %d\n", Factorial(2));
printf("3! = %d\n", Factorial(3));
printf("4! = %d\n", Factorial(4));
printf("9! = %d\n", Factorial(9));
return 0;
}
|
cs |
<실행결과>
2-2 재귀의 활용
재귀의 또다른 예로 피보나치 함수가 존재한다. 피보나치의 경우 0 1 1 2 3 5 8 13 21....로 1번째와 2번째를 제외하고 전 수와 전전 수를 합하여 현재의 수를 만드는 것이다. 이를 코드 적인 관점에서 생각하면 n이 1인 경우는 0, 2인 경우는 1로 설정하고 그 외의 경우는 n-1번째 수+ n-2번째 수로 하면 된다. 코드로 작성하면 다음과 같다.
<FibonacciFunc.c>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <stdio.h>
int Fibo(int num) {
if (num == 1) // 1번째인 경우 0 반환
return 0;
else if (num == 2) // 2번째인 경우 1 반환
return 1;
else // 그 외의 경우
return Fibo(num-1) + Fibo(num-2);
}
int main(void) {
for (int i = 1; i <= 15; i++) { // 피보나치 수 15개 출력
printf("%d ", Fibo(i));
}
return 0;
}
|
cs |
<실행결과>
앞선 포스팅에서 다루었던 이진 탐색의 경우 반복문을 통해 작성하였다. 이 또한 방금 배운 재귀를 이용하여 작성할 수 있다. 반복문에서는 while(first <= last) 의 조건을 통해 구현하였으니 이를 탈출 조건으로 작성하면 된다.
소스코드로 나타내면 다음과 같다.
<RecursiveBinarySearch.c>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <stdio.h>
int BSearchRecur(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 (arr[mid] > target) // mid의 값이 target보다 큰 경우 좌측에서 탐색해야함
return BSearchRecur(arr, first, mid - 1, target);
else // mid의 값이 target보다 작은 경우 우측에서 탐색해야함
return BSearchRecur(arr, mid + 1, last, target);
}
int main(void) {
int arr[] = { 1, 3, 5, 7, 9 };
int idx;
idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(int) - 1, 5);
if (idx == -1)
printf("탐색 실패 \n");
else
printf("타겟의 인덱스는 %d 입니다.\n", idx);
idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(int) - 1, 8);
if (idx == -1)
printf("탐색 실패 \n");
else
printf("타겟의 위치는 %d 입니다.\n", idx);
return 0;
}
|
cs |
<실행결과>
다만 이진탐색의 경우 중복으로 호출하는 구간이 존재하므로 코드의 시간 복잡도의 측면에서는 비효율적이다.
하노이 타워: The Tower of Hanoi
재귀함수의 또 다른 예시로 하노이 타워가 있다. 하노이 타워란 다음의 사이트에서 확인하길 바란다.
하노이의 탑 - 위키백과, 우리 모두의 백과사전
하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대
ko.wikipedia.org
어쨌든 우리가 알아야 할 것은 원반은 한 번에 하나만 옮길 수 있고 작은 원반 위에 큰 원반이 놓여서는 안 된다는 것이다. 이를 자세하게 살펴보면 하노이 역시 일련의 과정을 반복하므로 재귀를 통해 구현할 수 있다는 것을 알 수 있다.
간단하게만 알아보아도 될 예시이므로 바로 소스코드를 보인다.
<HanoiTowerSolu.c>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <stdio.h>
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) {
HanoiTowerMove(3, 'A', 'B', 'C');
return 0;
}
|
cs |
<실행결과>
'자료구조' 카테고리의 다른 글
| 5. 스택 (0) | 2022.01.10 |
|---|---|
| 4. 연결 리스트 (0) | 2021.07.19 |
| 3. 배열 기반 리스트 (0) | 2021.07.19 |
| 1. 자료구조와 알고리즘의 이해 (0) | 2021.06.27 |