개요
재귀 함수(Recursive Function)란 함수 내에서 자신을 다시 호출하는 함수를 말합니다.
재귀 함수는 반복적인 패턴을 보이는 문제를 쉽게 해결할 수 있게 해주는 방법으로 활용할 수 있습니다.재귀 함수의 활용
1. 피보나치 수열
피보나치 수열은 0, 1, 1, 2, 3, 5, 8 ... 과 같이 n-1과 n-2의 수를 더해가는 수열입니다.
피보나치 수열은 다음과 같은 규칙을 가집니다.
- n=1일 때, 0을 반환한다.
- n=2일 때, 1을 반환한다.
- 다른 경우, f(n-1) + f(n-2)의 값을 반환한다.
이를 재귀 함수를 사용하여 구현하면 다음과 같습니다.
#include <stdio.h>
int Fibonacci(int n)
{
if(n==1)
return 0;
else if(n==2)
return 1;
else
return Fibonacci(n-1) + Fibonacci(n-2);
}
int main(void) {
int i;
for(i=1; i<15; i++)
printf("%d ", Fibonacci(i));
return 0;
}2. 이진 탐색 알고리즘의 재귀적 구현
이진 탐색 알고리즘은 범위를 절반씩 줄여나가면서 탐색을 진행하는 알고리즘입니다. 반복문을 통해 구현할 수도 있지만 재귀 함수를 통해 구현할 수도 있습니다. 이진 탐색 알고리즘의 반복 패턴은 다음과 같습니다.
- 탐색 범위의 중앙에 목표 값이 저장되었는지 확인합니다.
- 저장되어 있지 않으면 탐색 범위를 반으로 줄여서 다시 탐색합니다.
탈출 조건은 시작 위치가 끝 위치보다 커졌을 때입니다. 이를 코드로 구현하면 다음과 같습니다.
#include <stdio.h>
int BSearch(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)
return BSearch(arr, first, mid-1, target);
else
return BSearch(arr, mid+1, last, target);
}
int main(void)
{
int arr[] = {1,2,3,4,5,6,7,8,9};
int result = BSearch(arr, 0, sizeof(arr)/sizeof(int), 2);
if(result == -1)
printf("탐색 실패(존재하지 않음)\n");
printf("탐색 결과:%d \n", result);
return 0;
}
3. 하노이 타워
하노이 타워는 재귀 함수의 힘이 돋보이는 문제입니다. 하노이 타워 문제는 '하나의 막대에 쌓여 있는 원반을 다른 막대에 그대로 옮기는 방법'에 관한 문제입니다. 그리고 다음과 같은 조건이 있습니다.
- 한 번에 하나의 원반을 옮길 수 있습니다.
- 옮기는 과정에서 작은 원반 위에 큰 원반을 올려놓을 수 없습니다.
이 문제 역시 반복 패턴을 찾아내면 재귀 함수로 쉽게 해결할 수 있습니다. 하노이 타워 문제의 반복 패턴은 무엇일까요? 연구해보도록 합시다.
아래와 같이 원반과 기둥이 준비되어 있습니다.
제일 바닥의 원반을 제외하고 가운데 막대로 옮깁니다.
그리고 바닥의 막대를 옮기고자 하는 막대로 옮깁니다.
그리고 가운데에 쌓여있는 원반들을 옮기고자 하는 막대로 옮깁니다.
이것이 하노이 타워 문제의 반복 패턴입니다. 중간에 원반 과정들의 이동 과정이 없다고 하실지도 모르겠습니다. 하지만 이것이 하노이 타워 문제 해결의 반복 패턴입니다. 정리하면 다음과 같습니다.
- 작원 원반 n-1개를 두 번째 막대로 옮깁니다.
- 가장 큰 원반을 세 번째 막대로 옮깁니다.
- 작은 원반 n-1개를 세 번째 막대로 옮깁니다.
이를 코드로 구현하면 다음과 같습니다.
#include <stdio.h>
void Hanoi(int num, char from, char by, char to)
{
if(num==1)
printf("원반 1을 %c에서 %c로 이동합니다.\n", from, to);
else
{
Hanoi(num-1, from, to, by); // 1단계
printf("원반 %d을(를) %c에서 %c로 이동합니다.\n", num, from, to); // 2단계
Hanoi(num-1, by, from, to); // 3단계
}
}
int main(void) {
Hanoi(3, 'A', 'B', 'C');
return 0;
}