재귀 함수
함수가 자기 자신을 호출하는 특별한 형태의 함수, 즉 재귀 함수(Recursive Function) 에 대해 알아보겠습니다.
재귀는 처음에는 다소 어렵게 느껴질 수 있지만, 특정 종류의 문제를 매우 우아하고 간결하게 해결할 수 있는 강력한 프로그래밍 기법입니다.
재귀 함수란 무엇인가?
재귀 함수는 자기 자신을 호출하여 작업을 수행하는 함수입니다.
마치 거울이 거울을 비추는 것처럼, 함수가 자신을 반복적으로 호출하며 문제를 해결해 나가는 방식입니다.
재귀 함수는 무한 루프에 빠지지 않기 위해 반드시 두 가지 요소를 포함해야 합니다.
- 기저 조건 (Base Case): 재귀 호출을 멈추는 조건입니다. 이 조건이 만족되면 함수는 더 이상 자신을 호출하지 않고, 결과를 반환하며 재귀 호출의 연속을 종료합니다. 모든 재귀 함수는 적어도 하나 이상의 기저 조건을 가져야 합니다.
- 재귀 단계 (Recursive Step): 함수가 자기 자신을 호출하는 부분입니다. 이때, 함수는 원래 문제보다 더 작고 간단한 버전의 문제를 해결하기 위해 자신을 호출해야 합니다. 이렇게 호출된 더 작은 문제의 해답들이 모여 최종 문제의 해답을 구성합니다.
재귀는 특히 다음과 같은 문제들을 해결하는 데 유용합니다.
- 프랙탈 구조: 자기 유사성(self-similarity)을 가진 구조.
- 트리 또는 그래프 탐색: 계층적이거나 연결된 데이터 구조.
- 분할 정복(Divide and Conquer) 알고리즘: 문제를 더 작은 하위 문제로 분할하여 해결하는 방식 (예: 퀵 정렬, 병합 정렬).
재귀 함수의 예시: 팩토리얼 계산
가장 고전적이고 이해하기 쉬운 재귀 함수의 예시는 팩토리얼(Factorial) 계산입니다.
n!은 n * (n-1) * (n-2) * ... * 1로 정의됩니다.
5! = 5 * 4 * 3 * 2 * 1- 또한,
5! = 5 * (4!)와 같이 정의할 수도 있습니다. 4! = 4 * (3!)1! = 1(기저 조건)0! = 1(기저 조건)
이 정의를 바탕으로 팩토리얼 함수를 재귀적으로 구현해 봅시다.
#include <iostream>
// n의 팩토리얼을 계산하는 재귀 함수
long long factorial(int n) {
// 1. 기저 조건 (Base Case): 재귀 호출을 멈추는 조건
if (n == 0 || n == 1) {
return 1;
}
// 2. 재귀 단계 (Recursive Step): 자신을 호출하며 더 작은 문제로 분할
else {
std::cout << "factorial(" << n << ") 호출: " << n << " * factorial(" << n - 1 << ")" << std::endl;
return n * factorial(n - 1);
}
}
int main() {
int num = 5;
std::cout << num << "! = " << factorial(num) << std::endl;
/* 출력 결과 (호출 과정):
factorial(5) 호출: 5 * factorial(4)
factorial(4) 호출: 4 * factorial(3)
factorial(3) 호출: 3 * factorial(2)
factorial(2) 호출: 2 * factorial(1)
5! = 120
*/
std::cout << "0! = " << factorial(0) << std::endl; // 출력: 0! = 1
return 0;
}factorial(5)의 실행 과정
factorial(5)호출.n은 5. 기저 조건 만족 안함.5 * factorial(4)반환 시도.factorial(4)호출.n은 4. 기저 조건 만족 안함.4 * factorial(3)반환 시도.factorial(3)호출.n은 3. 기저 조건 만족 안함.3 * factorial(2)반환 시도.factorial(2)호출.n은 2. 기저 조건 만족 안함.2 * factorial(1)반환 시도.factorial(1)호출.n은 1. 기저 조건 만족!1반환.factorial(2)는2 * 1(즉, 2)를 계산하고 반환.factorial(3)는3 * 2(즉, 6)를 계산하고 반환.factorial(4)는4 * 6(즉, 24)를 계산하고 반환.factorial(5)는5 * 24(즉, 120)를 계산하고 반환.
이 과정에서 각 factorial 호출은 스택에 쌓이고, 기저 조건에 도달하여 반환이 시작되면 역순으로 계산 결과가 풀려나가면서 스택에서 제거됩니다.
재귀 함수 예시: 피보나치 수열
피보나치 수열은 재귀의 또 다른 좋은 예시입니다.
피보나치 수열은 F(n) = F(n-1) + F(n-2)로 정의되며, F(0) = 0, F(1) = 1이 기저 조건입니다.
#include <iostream>
// n번째 피보나치 수를 계산하는 재귀 함수
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() {
for (int i = 0; i < 10; ++i) {
std::cout << "fibonacci(" << i << ") = " << fibonacci(i) << std::endl;
}
/* 출력:
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
fibonacci(7) = 13
fibonacci(8) = 21
fibonacci(9) = 34
*/
return 0;
}피보나치 함수는 factorial보다 더 복잡한 재귀 호출 구조를 가집니다.
fibonacci(5)를 계산하기 위해 fibonacci(4)와 fibonacci(3)을 호출하고, fibonacci(4)는 다시 fibonacci(3)과 fibonacci(2)를 호출하는 등, 동일한 계산이 여러 번 반복될 수 있습니다.
이는 재귀 함수의 잠재적인 비효율성을 보여줍니다.
재귀 함수 사용 시 주의사항
재귀 함수는 강력하고 우아하지만, 잘못 사용하면 심각한 문제를 야기할 수 있습니다.
-
스택 오버플로우 (Stack Overflow): 각 함수 호출은 프로그램의 호출 스택(call stack)에 메모리를 할당합니다. 재귀 호출이 너무 깊어지거나 (기저 조건에 도달하지 못하거나), 너무 많은 스택 메모리를 사용하게 되면, 할당된 스택 공간을 초과하여 스택 오버플로우 오류가 발생하고 프로그램이 비정상적으로 종료됩니다.
factorial(10000)과 같이 큰 숫자를 재귀로 계산하려 하면 대부분의 시스템에서 스택 오버플로우가 발생할 것입니다. -
비효율성 (Inefficiency): 위 피보나치 수열 예시처럼, 동일한 서브 문제를 여러 번 반복해서 계산하는 경우 재귀 함수는 비효율적일 수 있습니다. 이 경우, 반복문(Iteration)으로 구현하거나, 메모이제이션(Memoization)(계산 결과를 저장하여 중복 계산을 피하는 기법)을 적용하여 성능을 개선할 수 있습니다.
피보나치 수열 반복문으로 구현 int fibonacciIterative(int n) { if (n <= 0) return 0; if (n == 1) return 1; int a = 0; int b = 1; int result = 0; for (int i = 2; i <= n; ++i) { result = a + b; a = b; b = result; } return result; } -
기저 조건의 누락 또는 오류: 기저 조건이 없거나 잘못되면, 재귀 함수는 무한히 자기 자신을 호출하게 되어 결국 스택 오버플로우로 이어집니다.
재귀 vs 반복
모든 재귀 함수는 반복문으로 변환될 수 있고 모든 반복문은 재귀 함수로 변환될 수 있습니다.
둘 중 어떤 것을 사용할지는 문제의 특성, 코드의 가독성, 그리고 성능 고려 사항에 따라 달라집니다.
-
재귀
- 장점: 재귀적으로 정의된 문제(예: 트리 순회, 프랙탈)를 간결하고 우아하게 표현할 수 있습니다. 코드가 직관적이고 이해하기 쉬울 수 있습니다.
- 단점: 스택 오버플로우 위험, 반복문보다 느리거나 비효율적일 수 있음.
-
반복
- 장점: 일반적으로 재귀보다 빠르고 메모리 효율적입니다. 스택 오버플로우 위험이 없습니다.
- 단점: 특정 문제(예: 트리 순회)에서는 재귀보다 코드가 복잡해지거나 직관적이지 않을 수 있습니다.
핵심: 재귀 함수를 사용할 때는 항상 기저 조건을 명확히 설정하고, 각 재귀 호출이 원래 문제보다 더 작은 문제로 나아가는지 확인하여 무한 재귀에 빠지지 않도록 주의해야 합니다. 성능이 중요한 경우에는 재귀 대신 반복문을 고려하거나, 메모이제이션 같은 최적화 기법을 적용해야 합니다.