728x90
C++ 재귀 함수에 대한 설명
재귀(Recursion)는 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법
재귀 함수의 기본 구조
void recursiveFunction() {
// 종료 조건 (Base Case)
if (/* 조건 */) {
return;
}
// 자기 자신 호출 (Recursive Case)
recursiveFunction();
}
- Base Case (종료 조건): 재귀 호출을 멈추는 조건, 종료 조건이 없으면 무한 루프가 발생하여 프로그램이 중단됨
- Recursive Case (재귀 호출): 함수가 자기 자신을 호출하여 문제를 더 작은 단위로 해결
재귀 함수 예제
1. 팩토리얼 계산
팩토리얼은 n! = n * (n-1) * (n-2) * ... * 1을 의미합니다.
#include <iostream>
int factorial(int n) {
if (n == 0 || n == 1) { // 종료 조건
return 1;
}
return n * factorial(n - 1); // 자기 자신 호출
}
int main() {
int n = 5;
std::cout << "Factorial of " << n << " is: " << factorial(n) << std::endl;
// Factorial of 5 is: 120
return 0;
}
2. 피보나치 수열
피보나치 수열은 다음과 같은 수열입니다: 0, 1, 1, 2, 3, 5, 8, 13, ...
#include <iostream>
int fibonacci(int n) {
if (n == 0) return 0; // 종료 조건
if (n == 1) return 1; // 종료 조건
return fibonacci(n - 1) + fibonacci(n - 2); // 재귀 호출
}
int main() {
int n = 10;
for (int i = 0; i < n; i++) {
std::cout << fibonacci(i) << " ";
}
// 0 1 1 2 3 5 8 13 21 34
return 0;
}3. 하노이 탑 문제
하노이 탑 문제는 재귀의 대표적인 예제입니다. N개의 원반을 출발지에서 목표지로 이동시키는 과정입니다.
#include <iostream>
void hanoi(int n, char from, char to, char aux) {
if (n == 1) { // 종료 조건
std::cout << "Move disk 1 from " << from << " to " << to << std::endl;
return;
}
hanoi(n - 1, from, aux, to); // n-1개의 원반을 보조 기둥으로 이동
std::cout << "Move disk " << n << " from " << from << " to " << to << std::endl;
hanoi(n - 1, aux, to, from); // n-1개의 원반을 목표 기둥으로 이동
}
int main() {
int n = 3; // 원반의 개수
hanoi(n, 'A', 'C', 'B'); // 출발지: A, 목표지: C, 보조 기둥: B
return 0;
}
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
재귀와 반복문의 차이점
특징 재귀 반복문
| 가독성 | 복잡한 문제를 간결하고 직관적으로 표현 가능 | 코드가 더 길어질 수 있음 |
| 성능 | 함수 호출로 인해 오버헤드가 발생할 수 있음 | 더 빠르고 효율적 |
| 사용 사례 | 분할 정복, 트리 탐색, 하노이 탑 등 | 단순 반복 작업 |
| 메모리 사용 | 호출 스택에 추가 메모리를 사용 | 메모리 사용량 적음 |
재귀를 반복문으로 변환
피보나치 수열의 재귀 코드는 성능이 비효율적입니다. 이를 반복문으로 변환하면 성능이 개선됩니다.
반복문 예제:
#include <iostream>
int fibonacciIterative(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int prev = 0, curr = 1, next;
for (int i = 2; i <= n; i++) {
next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
int main() {
int n = 10;
std::cout << "Fibonacci(" << n << ") = " << fibonacciIterative(n) << std::endl;
return 0;
}
728x90