핵심 정리
csharp
int Factorial(int n)
{
if (n <= 1) return 1; // 기저 조건
return n * Factorial(n - 1); // 더 작은 문제
}| 요소 | 확인할 질문 |
|---|---|
| 기저 조건 | 언제 멈추는가 |
| 재귀 호출 | 문제가 더 작아지는가 |
| 반환값 | 아래 호출의 결과를 어떻게 합치는가 |
| 상태 | 매 호출마다 무엇이 달라지는가 |
| 깊이 | 콜 스택을 넘치게 하지 않는가 |
구조
재귀는 함수가 자기 자신을 호출하는 문법보다 문제를 같은 모양의 더 작은 문제로 바꾸는 방식입니다. 핵심은 호출이 반복될수록 반드시 기저 조건에 가까워져야 한다는 점입니다.
csharp
int Sum(int n)
{
if (n == 0) return 0;
return n + Sum(n - 1);
}이 코드는 아래처럼 쌓였다가 역순으로 풀립니다.
text
Sum(3)
3 + Sum(2)
2 + Sum(1)
1 + Sum(0)
0각 호출은 지역 변수, 매개변수, 돌아갈 위치를 가진 스택 프레임을 만듭니다. 그래서 재귀 깊이가 깊어지면 시간뿐 아니라 스택 메모리도 사용합니다.
기저 조건이 먼저다
재귀 문제를 풀 때는 호출식을 먼저 쓰기보다 멈추는 조건을 먼저 잡는 편이 안전합니다.
csharp
int Fibonacci(int n)
{
if (n <= 1) return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}위 코드는 형태는 단순하지만 같은 값을 반복 계산하므로 시간 복잡도가 급격히 커집니다. 재귀라고 해서 항상 느린 것은 아니지만, 중복 하위 문제가 있는 재귀는 메모이제이션이나 반복 DP로 바꿔야 합니다.
반복으로 바꾸는 기준
| 상황 | 재귀 유지 | 반복 전환 |
|---|---|---|
| 트리, DFS, 백트래킹 | 구조가 자연스러움 | 깊이가 크면 스택 직접 관리 |
| 단순 누적 | 읽기 쉬울 때만 | 반복문이 보통 더 안전 |
| 중복 계산 | 메모이제이션 필요 | DP 테이블로 전환 가능 |
| 입력 깊이가 큼 | 스택 오버플로 위험 | Stack<T> 사용 검토 |
재귀를 반복으로 바꾸면 호출 스택이 명시적인 자료구조로 바뀝니다.
csharp
var stack = new Stack<int>();
stack.Push(start);
while (stack.Count > 0)
{
int current = stack.Pop();
// current 처리 후 다음 상태 push
}주의할 점
C#은 일반적인 코테 환경에서 깊은 재귀에 취약할 수 있습니다. 입력 크기가 수만 이상이고 경로처럼 한쪽으로 길게 이어질 수 있다면 재귀 DFS 대신 Stack<T>를 쓰는 반복 DFS를 먼저 검토하세요.
또 재귀 함수의 매개변수에 큰 배열이나 문자열을 매번 새로 만들어 넘기면 호출 수보다 복사 비용이 더 큰 문제가 될 수 있습니다.
참고 링크
2 sources