재귀함수(Recursion Function)

재귀 함수는 자료구조와 알고리즘에서 매우 중요한 개념입니다. 복잡한 알고리즘을 간결하고 우아하게 표현할 수 있게 해주는 강력한 도구입니다.

정의와 특징

• 재귀 함수는 자기 자신을 호출하는 함수입니다.
• 주로 문제를 더 작은 동일한 형태의 부분 문제로 나누어 해결하는 방식으로 작동합니다.
• 반복되는 수학적 관계식을 직관적으로 구현할 수 있습니다.

재귀 함수의 구조

1. 기저 사례 (Base case): 재귀 호출을 멈추는 조건
2. 재귀 단계 (Recursive step): 문제를 더 작은 문제로 축소하고 자기 자신을 호출하는 부분

예시

1. 이진 탐색

int BSearch(vector<int> a, int first, int last, int target)
{
    int mid;
    if (first > last) return -1;//탈출 조건

    mid = (first + last) / 2;

    if (a[mid] == target) return mid;//탈출 조건

    else if (a[mid] > target)
    {
        return BSearch(a, first, mid - 1, target);//재귀 단계
    }
    else
    {
        return BSearch(a, mid + 1, last, target);//재귀 단계
    }
}

 

2. 하노이 탑

void HanoiTowerMove(int num, char from, char by, char to)
{
    if (num == 1)//탈출 조건
    {
        cout << "원반1을 " << from << "에서 " << to << "로 이동 \n";
    }
    else//재귀 단계
    {
        HanoiTowerMove(num - 1, from, to, by);
        cout << "원반" << num << "을 " << from << "에서 " << to << "로 이동 \n";
        HanoiTowerMove(num - 1, by, from, to);
    }
}

장단점

장점:

• 복잡한 문제를 간결하고 이해하기 쉬운 코드로 표현 가능
• 일부 알고리즘(예: 트리 순회, 퀵 정렬)에서 매우 효율적

단점:

• 메모리 사용량이 많을 수 있음 (호출 스택 오버플로우 위험)
• 동일한 계산을 반복하여 성능이 저하될 수 있음
• 깊은 재귀는 스택 오버플로우를 일으킬 수 있음

최적화 기법

1. 꼬리 재귀 (Tail recursion): 컴파일러 최적화를 통해 반복문처럼 효율적으로 실행 가능
2. 메모이제이션 (Memoization): 이전 계산 결과를 저장하여 중복 계산 방지

재귀 함수는 강력한 도구이지만, 상황에 따라 적절히 사용해야 합니다. 때로는 반복문이나 동적 프로그래밍으로 대체하여 성능을 개선할 수 있습니다.