[Algorithm] 재귀함수

재귀함수

재귀함수(Recursive_Function)은 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법입니다.

재귀 호출이나 되부름이라고도 합니다.

큰 문제를 작은 하위 문제로 분할하여 해결할 때 유용합니다.

코드가 간결해지지만, 스택 메모리를 사용하여 너무 깊어지면 스택 오버플로우와 속도 측면에서 속도 저하가 발생 할 수 있습니다.

for, while 등의 반복문으로 구현 가능한 로직은 모두 재귀함수로도 가능하고 이 반대로도 가능합니다.
구체적인 차이는 다음과 같습니다.

구분	반복문	재귀
방식	반복	함수 호출
메모리	적게 사용	스택 사용
속도	빠름	상대적으로 느림
가독성	복잡할 수 있음	간결함

구성 요소

재귀 함수는 반드시 다음 두 가지로 구성됩니다.

1. 종료 조건(Base Case)
   • 재귀 호출을 멈추는 조건
2. 재귀 호출(Recursive Case)
   • 문제를 더 작은 문제로 나누어 자기 자신을 호출하는 부분

예시

재귀 함수를 설명할 때 가장 많이 등장하는 예제 코드 중 하나인 팩토리얼 구하기로 예시를 들어보겠습니다.

#include <iostream>

int factorial(int n)
{
    // 종료 조건
    if (n == 0)
    {
        return 1;
    }

    // 재귀 호출
    return n * factorial(n - 1);
}

int main()
{
    // 120 출력
    std::cout << factorial(5) << std::endl;
}

위의 코드를 실행할 경우 실행 흐름은 다음과 같습니다.

1. factorial(5) 호출
2. n != 0이므로, 재귀호출 -> factorial(4)
3. n != 0이므로, 재귀호출 -> factorial(3)
4. n != 0이므로, 재귀호출 -> factorial(2)
5. n != 0이므로, 재귀호출 -> factorial(1)
6. n != 0이므로, 재귀호출 -> factorial(0)
7. n == 0이므로, factorial(0)에서 1 반환
8. factorial(1)은 factorial(0)의 반환값을 전달받아, 1 * 1을 계산하고 1 반환
9. factorial(2)은 factorial(1)의 반환값을 전달받아, 2 * 1을 계산하고 2 반환
10. factorial(3)은 factorial(2)의 반환값을 전달받아, 3 * 2을 계산하고 6 반환
11. factorial(4)은 factorial(3)의 반환값을 전달받아, 4 * 6을 계산하고 24 반환
12. factorial(5)은 factorial(4)의 반환값을 전달받아, 함수에서 5 * 24 반환
13. 출력 120

재귀함수를 사용하는 경우

• 트리 구조 탐색
  • DFS
• 분할 정복
  • Merge Sort, Quick Sort
• 백트래킹
  • N-Queen, 조합/순열
• 구조 자체가 재귀적인 문제