C++ 재귀 함수 마스터하기: 개념, 예제, 모범 사례

C++ 재귀 함수 마스터하기

이 튜토리얼에서는 C++ 재귀 함수를 탐구하고, 어떻게 동작하는지 이해하며, 실전 예제를 통해 활용법을 배웁니다.

자기 자신을 호출하는 함수를 재귀 함수(Recursive Function)라 합니다. 이 강력한 기법을 재귀(Recursion)라고 부릅니다.

---

C++에서 재귀가 동작하는 원리

void recurse()
{
    // 재귀 전 코드
    recurse(); // 재귀 호출
    // 재귀 후 코드
}

int main()
{
    // 설정 코드
    recurse();
    // 정리 코드
}

아래 그림은 재귀의 반복적 자기 호출 특성을 보여줍니다.

재귀는 **기저 조건(Base Condition)**이 만족될 때까지 계속됩니다.

무한 재귀를 막으려면 조건문(예: if…else)으로 재귀 호출을 수행할 분기 하나만 두어야 합니다.

---

예제 1: 팩토리얼 재귀 계산

// n! = 1 × 2 × … × n 계산
#include <iostream>
using namespace std;

int factorial(int);

int main()
{
    int n, result;
    cout << "Enter a non-negative number: ";
    cin >> n;
    result = factorial(n);
    cout << "Factorial of " << n << " = " << result;
    return 0;
}

int factorial(int n)
{
    if (n > 1)
        return n * factorial(n - 1);
    else
        return 1;
}

실행 결과

Enter a non-negative number: 4
Factorial of 4 = 24

---

팩토리얼 프로그램 동작 원리

factorial() 함수는 자기 자신을 반복 호출하며 매번 n을 1씩 줄입니다. n이 1 이하로 떨어지면 1을 반환하고, 재귀가 풀리면서 최종 결과가 계산됩니다.

---

C++에서 재귀 사용의 장단점

재귀의 주요 장점과 단점:

---

장점

• 간결하고 표현력 높은 코드 작성 가능
• 트리, 그래프, 조합 탐색 등 본질적으로 재귀적인 문제의 자연스러운 해결책

---

단점

• 동등한 반복적 접근보다 더 많은 스택 공간 소비
• 추가 프로세서 오버헤드 발생 가능
• 깊은 호출 스택으로 디버깅이 더 어려울 수 있음

---

재귀를 언제, 어떻게 쓸지 이해하면 일반적인 함정을 피하면서 더 깔끔하고 유지보수하기 좋은 C++ 코드를 작성할 수 있습니다.