🥹 알고리즘 문제를 풀다보면 재귀함수를 호출해야하는 경우가 많은데, 이번 글에서 확실하게 풀고 넘어가려고 한다.
(이제부터 헷갈리기는 이 글을 마지막으로 꼭 끝내자!)
📌재귀 호출이란?
재귀 호출이라 하면 알다시피 함수 내에서 또 해당 함수가 호출되는 것을 뜻한다. 그러면 내가 어려워하는 부분은 무엇일까?
재귀함수는 계속해서 반복하는 함수이기 때문에, 꼭 '기저조건'이 필요하다. 즉 함수를 끝낼 수 있는 조건을 말한다.
간단한 재귀 예제를 풀고 이해해보자. 다음은 팩토리얼을 재귀함수를 이용한 코드 풀이이다.
👉 팩토리얼 (Factorial) 재귀함수 코드
public class FactorialExample {
public static int factorial(int n) {
if (n == 1) return 1; // 기저 조건 (Base Case)
return n * factorial(n - 1); // 재귀 호출
}
public static void main(String[] args) {
System.out.println(factorial(5)); // 출력: 5! = 120
}
}위 코드를 시각화 하면 다음과 같다.
factorial(5)
→ 5 * factorial(4)
→ 5 * (4 * factorial(3))
→ 5 * (4 * (3 * factorial(2)))
→ 5 * (4 * (3 * (2 * factorial(1))))
→ 5 * 4 * 3 * 2 * 1 → 120
즉, 이렇게 반복되어 호출되는 것을 재귀호출이라고 한다. 하지만, 이보다 더 복잡한 코드에 쓰이는 재귀함수도 있다.
백준 2961번의 부분집합(Subset) 문제를 예를 들어보자. 이 문제의 재귀함수 부분 풀이는 다음과 같다.
👉 부분집합(Subset) 재귀함수 코드
🛠 예제: N = 3일 때 부분집합 구하는 과정 (select[i] 배열을 이용해 true(선택 O), false(선택 X)로 부분집합을 만든다.)
// 부분집합을 구하는 재귀 호출
void subset(int idx) {
if (idx == N) {
// 선택된 조합 출력
return;
}
select[idx] = true; // 선택 O
subset(idx + 1);
select[idx] = false; // 선택 X
subset(idx + 1);
}subset(0)
→ select[0] = true → subset(1)
→ select[1] = true → subset(2)
→ select[2] = true → subset(3) → [O O O] ✅
→ select[2] = false → subset(3) → [O O X] ✅
→ select[1] = false → subset(2)
→ select[2] = true → subset(3) → [O X O] ✅
→ select[2] = false → subset(3) → [O X X] ✅
→ select[0] = false → subset(1)
→ select[1] = true → subset(2)
→ select[2] = true → subset(3) → [X O O] ✅
→ select[2] = false → subset(3) → [X O X] ✅
→ select[1] = false → subset(2)
→ select[2] = true → subset(3) → [X X O] ✅
→ select[2] = false → subset(3) → [X X X] ✅
이렇게 모든 조합을 방문하는 것을 재귀함수라고 한다. 먼저 첫번째 재귀함수를 방문하고 모두 ture가 되면, 다음 재귀함수 코드로 이동해 하나씩 false를 만들어 조합하는 과정이다.
🚀 위 코드의 재귀 호출 흐름 다시 확인해보자!
1. select[0] = true부터 시작해서 끝까지 true를 채움
2. 그다음 false로 하나씩 변경하면서 모든 경우의 수 탐색
📌 핵심 흐름 요약
1. select[0] = true로 두고, 끝까지 내려가서 모두 true로 방문
2. select[2]부터 false로 바꿔 하나씩 조합 생성
3. select[1] = false로 변경하고 다시 select[2]를 true/false로 바꿔가며 조합
4. 마지막으로 select[0] = false로 변경 후, select[1], select[2] 조합을 반복
'Q&A' 카테고리의 다른 글
| 동기와 비동기의 차이점은? (0) | 2025.03.01 |
|---|
