C++ 재귀 함수

1. 개요

1.1 문서 개요

이 문서는 C++의 재귀 함수(recursive function)에 관해 기록하는 문서입니다. 재귀 함수는 자기 자신을 호출함으로써 반복적 문제 해결 구조를 간결하게 구현할 수 있는 함수 방식입니다.

2. 내용

2.1 재귀 함수의 기본 개념

2.1.1 정의

재귀 함수는 함수 내부에서 자기 자신을 다시 호출하는 함수를 의미합니다. 일반적으로 하나 이상의 종료 조건과 재귀 호출문으로 구성됩니다.

2.2 재귀 함수 예시

2.2.1 팩토리얼 계산

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

2.2.2 피보나치 수열

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

2.3 재귀의 조건

2.3.1 종료 조건

무한 재귀 호출을 방지하기 위해 if 문 등을 사용하여 반드시 종료 조건을 명시해야 합니다.

2.3.2 스택 메모리 제한

함수 호출 시마다 스택이 쌓이므로, 너무 깊은 재귀는 스택 오버플로우를 유발할 수 있습니다.

2.4 재귀와 반복의 비교

• 재귀는 코드 표현이 간결
• 반복은 성능상 유리
• Tail Recursion이 지원되지 않는 C++에서는 반복이 더 안전한 경우가 많음

3. 마무리

C++ 재귀 함수는 자기 자신을 호출함으로써 반복 구조를 명시적으로 표현할 수 있는 방식입니다. 종료 조건과 재귀 구조의 정확한 설계가 필요하며, 알고리즘 구현에서 수학적, 계층적 문제 처리에 유용하게 사용됩니다.