재귀함수(Recursive Function)

재귀함수(Recursive Function)는 자기 자신을 호출하는 함수입니다. 이를 통해 하나의 큰 문제를 작은 문제로 분할하고, 이를 해결한 후 이를 합쳐서 큰 문제를 해결하는 방식으로 프로그램을 작성할 수 있습니다. C언어에서 재귀함수는 함수 내에서 자신을 호출하는 방식으로 구현할 수 있습니다.

재귀함수는 보통 하나 이상의 종료 조건(Base Case)과 하나 이상의 재귀 호출(Recursive Call)로 구성됩니다. 종료 조건은 재귀 호출이 멈추는 지점을 나타내며, 재귀 호출은 큰 문제를 작은 문제로 분할하여 해결하는 역할을 합니다.

재귀함수를 사용할 때는 몇 가지 주의할 점이 있습니다. 먼저, 재귀함수의 호출은 스택(Stack) 구조로 이루어지기 때문에, 호출 횟수가 많아질수록 메모리 사용량이 증가합니다. 따라서, 너무 많은 재귀 호출을 사용할 경우 스택 오버플로(Stack Overflow)가 발생할 수 있습니다. 또한, 재귀함수의 코드는 반복문을 사용하는 코드보다 이해하기 어렵고 느리게 동작할 수 있습니다.

 

 

아래는 재귀함수로 풀기 좋을만한 몇 가지 주제를 살펴보겠습니다.

 

 

1. 이진 탐색(Binary Search) 

이진 탐색은 정렬된 리스트에서 원하는 값을 찾는 알고리즘입니다.   

#include <stdio.h>

int binary_search(int arr[], int start, int end, int target) {
    if (start > end) {
        return -1;
    }
    
    int mid = (start + end) / 2;
    
    if (arr[mid] == target) {
        return mid;
    }
    else if (arr[mid] > target) {
        return binary_search(arr, start, mid - 1, target);
    }
    else {
        return binary_search(arr, mid + 1, end, target);
    }
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(int);
    int target = 5;
    int result = binary_search(arr, 0, n - 1, target);
    
    if (result == -1) {
        printf("원소를 찾을 수 없습니다.\n");
    }
    else {
        printf("원소의 인덱스는 %d입니다.\n", result);
    }
    
    return 0;
}

 

2. 피보나치 수열(Fibonacci Sequence) 

피보나치 수열은 0과 1로 시작하여, 이전 두 개의 항을 더한 값을 다음 항으로 하는 수열입니다. 

#include <stdio.h>

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

int main() {
    int n = 10;
    int result = fibonacci(n);
    
    printf("%d번째 피보나치 수열은 %d입니다.\n", n, result);
    
    return 0;
}

 

3. 하노이의 탑(Hanoi Tower)

하노이의 탑은 원반이 세 개의 기둥에 꽂혀 있을 때, 첫 번째 기둥의 원반들을 세 번째 기둥으로 옮기는 문제입니다. 
재귀함수를 사용하여 구현할 수 있습니다. 

#include <stdio.h>

void hanoi(int n, char from, char to, char temp) {
    if (n == 1) {
        printf("%c에서 %c로 원반 %d을 이동합니다.\n", from, to, n);
    }
    else {
        hanoi(n - 1, from, temp, to);
        printf("%c에서 %c로 원반 %d을 이동합니다.\n", from, to, n);
        hanoi(n - 1, temp, to, from);
    }
}

int main() {
    int n = 3;
    
    hanoi(n, 'A', 'C', 'B');
    
    return 0;
}

 

4. 이항 계수(Binomial Coefficient)

이항 계수는 주어진 n과 k에 대해 n개의 원소 중 k개를 뽑을 때의 경우의 수를 계산하는 공식입니다. 

#include <stdio.h>

int binomial(int n, int k) {
    if (k == 0 || k == n) {
        return 1;
    }
    else {
        return binomial(n - 1, k - 1) + binomial(n - 1, k);
    }
}

int main() {
    int n = 5;
    int k = 2;
    int result = binomial(n, k);
    
    printf("%d개의 원소 중 %d개를 뽑을 때의 경우의 수는 %d입니다.\n", n, k, result);
    
    return 0;
}

 

위 예제 코드들은 각각 이진 탐색, 피보나치 수열, 하노이의 탑, 이항 계수를 재귀함수를 사용하여 구현한 것입니다. 재귀함수를 사용하면 코드의 간결함과 가독성을 높일 수 있습니다. 또한, 문제의 구조를 재귀적으로 표현하면 문제 해결에 용이합니다. 단, 재귀함수를 사용할 때는 종료 조건을 잘 설정하여 무한 반복에 빠지지 않도록 주의해야 합니다.