재귀와 반복: 상태 전개의 두 가지 방식
같은 문제를 재귀로도, 반복문으로도 풀 수 있는 경우가 많습니다. 처음에는 두 방식이 완전히 다른 기술처럼 보이지만, 실제 동작 흐름은 매우 비슷합니다. 둘 다 현재 상태에서 다음 상태로 이동한다는 전이를 반복합니다.
차이는 상태를 어디에 저장하느냐입니다. 재귀는 호출 스택을 사용하고, 반복은 스택/큐/변수를 직접 관리합니다. 여기서는 문법보다 내 문제에서 어떤 방식이 더 안전한가를 판단하는 기준을 다룹니다.
핵심 패턴 요약
재귀와 반복은 본질적으로 같은 상태 전이를 다른 저장 방식으로 실행합니다. 지금 푸는 문제를 기준으로 최대 깊이와 필요한 보조 공간을 우선 적고 읽어 보세요.
재귀는 함수를 다시 호출하면서 문제 크기를 줄여 가는 방식입니다.
정확한 구현 기준은 종료 조건과 자기 호출 규칙(점화식)을 명확히 두는 것입니다.
트리 DFS에서 dfs(node)가 자식에게 다시 dfs를 호출하는 흐름이 대표 예시입니다.
반복은 for/while과 보조 자료구조로 상태를 직접 갱신하는 방식입니다.
정의로 보면 명시적 제어 구조와 저장소를 통해 전이를 단계적으로 수행하는 구현입니다.
DFS를 스택으로 만들면 pop한 노드의 이웃을 push하면서 재귀와 같은 순회를 재현할 수 있습니다.
상태 저장소는 아직 처리하지 않은 상태를 잠깐 모아 두는 공간입니다. 탐색 순서와 메모리 사용량은 어떤 저장소를 쓰는지에 따라 달라집니다. 재귀 DFS는 호출 스택을 쓰고, 반복 DFS는 명시적 스택을 써서 같은 문제를 해결합니다.
재귀/반복 선택 실패 사례와 연결하기
재귀/반복 선택이 잘못되면 다음 문제가 발생합니다.
- 깊은 입력에서 스택 오버플로우
- 반복 구현에서 상태 누락으로 잘못된 결과
- 코드는 동작하지만 유지보수성이 급격히 저하
정답 여부뿐 아니라 운영 안정성과 디버깅 비용도 같이 달라집니다. 지금 문제의 최대 입력 깊이를 적고, 재귀 한계와 비교해 보세요.
상태 전개 테스트로 빠르게 검증하기
학습 효율을 높이려면 오답 -> 디버깅 -> 교정 -> 검증 순서로 로그를 남기면서 진행하는 것이 가장 빠릅니다.
아래 그래프를 기준으로 재귀 DFS와 반복 DFS의 상태 변화를 비교합니다.
- 그래프:
1 -> [2,3],2 -> [4],3 -> [5] - 시작 정점:
1
- 재귀 DFS는 호출 스택이
1 -> 2 -> 4순서로 쌓였다가 되돌아옵니다. - 반복 DFS는 명시적 스택에 다음 정점을 push/pop 하며 같은 방문 순서를 만듭니다.
- 중요한 차이는 상태 저장 위치이며, 방문 체크 시점이 늦으면 중복 방문이 발생합니다.
재귀 DFS
문제 의도: 호출 스택 기반 상태 전개가 어떻게 DFS 순회를 만드는지 확인합니다.
입력 예시: graph={1:[2,3],2:[4],3:[5],4:[],5:[]}, start=1
출력 예시: 1 2 4 3 5
push/add/append는 방문한 노드를 결과 리스트 뒤에 붙이는 연산입니다.
#include <iostream>
#include <vector>
using namespace std;
void dfsRecursive(
int node,
const vector<vector<int>>& graph,
vector<bool>& visited,
vector<int>& order
) {
if (visited[node]) return;
visited[node] = true;
order.push_back(node);
for (int nxt : graph[node]) {
dfsRecursive(nxt, graph, visited, order);
}
}
int main() {
vector<vector<int>> graph(6);
graph[1] = {2, 3};
graph[2] = {4};
graph[3] = {5};
graph[4] = {};
graph[5] = {};
vector<bool> visited(6, false);
vector<int> order;
dfsRecursive(1, graph, visited, order);
for (int x : order) cout << x << " ";
cout << "\n";
return 0;
}import java.util.*;
public class Main {
static void dfsRecursive(
int node,
List<List<Integer>> graph,
boolean[] visited,
List<Integer> order
) {
if (visited[node]) return;
visited[node] = true;
order.add(node);
for (int nxt : graph.get(node)) {
dfsRecursive(nxt, graph, visited, order);
}
}
public static void main(String[] args) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= 5; i++) graph.add(new ArrayList<>());
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(2).add(4);
graph.get(3).add(5);
boolean[] visited = new boolean[6];
List<Integer> order = new ArrayList<>();
dfsRecursive(1, graph, visited, order);
System.out.println(order); // [1, 2, 4, 3, 5]
}
}graph = [
[],
[2, 3],
[4],
[5],
[],
[],
]
def dfs_recursive(node, visited, order):
if visited[node]:
return
visited[node] = True
order.append(node)
for nxt in graph[node]:
dfs_recursive(nxt, visited, order)
visited1 = [False] * 6
order1 = []
dfs_recursive(1, visited1, order1)
print(order1) # [1, 2, 4, 3, 5]fn dfs_recursive(
node: usize,
graph: &Vec<Vec<usize>>,
visited: &mut Vec<bool>,
order: &mut Vec<usize>,
) {
if visited[node] {
return;
}
visited[node] = true;
order.push(node);
for &nxt in &graph[node] {
dfs_recursive(nxt, graph, visited, order);
}
}
fn main() {
let graph: Vec<Vec<usize>> = vec![
vec![],
vec![2, 3],
vec![4],
vec![5],
vec![],
vec![],
];
let mut visited: Vec<bool> = vec![false; 6];
let mut order: Vec<usize> = Vec::new();
dfs_recursive(1, &graph, &mut visited, &mut order);
println!("{:?}", order);
}재귀/반복 전개 결과 기초 조건 확인
재귀는 문제 정의를 코드로 직접 표현하기 좋습니다.
현재 노드를 방문하고 이웃을 재귀 호출한다는 구조가 자연스럽습니다.
하지만 입력 깊이가 커지면 호출 스택 한계에 걸릴 수 있습니다.
- 평균 시간복잡도:
O(V + E) - 최악 시간복잡도:
O(V + E) - 공간복잡도:
O(V)(방문 집합 + 호출 스택)
반복 DFS
문제 의도: 명시적 스택으로 재귀 없이 동일한 DFS 순회를 구현합니다.
입력 예시: graph={1:[2,3],2:[4],3:[5],4:[],5:[]}, start=1
출력 예시: 1 2 4 3 5 (push 순서에 따라 달라질 수 있음)
pop은 스택의 맨 뒤 값을 꺼내는 연산으로, DFS 진행 순서를 결정합니다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> dfsIterative(int start, const vector<vector<int>>& graph) {
vector<bool> visited(6, false);
vector<int> stack = {start};
vector<int> order;
while (!stack.empty()) {
int node = stack.back();
stack.pop_back();
if (visited[node]) continue;
visited[node] = true;
order.push_back(node);
const vector<int>& nexts = graph[node];
for (int i = static_cast<int>(nexts.size()) - 1; i >= 0; --i) {
int nxt = nexts[i];
if (!visited[nxt]) stack.push_back(nxt);
}
}
return order;
}
int main() {
vector<vector<int>> graph(6);
graph[1] = {2, 3};
graph[2] = {4};
graph[3] = {5};
graph[4] = {};
graph[5] = {};
vector<int> order = dfsIterative(1, graph);
for (int x : order) cout << x << " ";
cout << "\n";
return 0;
}import java.util.*;
public class Main {
static List<Integer> dfsIterative(int start, List<List<Integer>> graph) {
boolean[] visited = new boolean[6];
List<Integer> stack = new ArrayList<>();
List<Integer> order = new ArrayList<>();
stack.add(start);
while (stack.size() > 0) {
int node = stack.remove(stack.size() - 1);
if (visited[node]) continue;
visited[node] = true;
order.add(node);
List<Integer> nexts = graph.get(node);
for (int i = nexts.size() - 1; i >= 0; i--) {
int nxt = nexts.get(i);
if (!visited[nxt]) stack.add(nxt);
}
}
return order;
}
public static void main(String[] args) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= 5; i++) graph.add(new ArrayList<>());
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(2).add(4);
graph.get(3).add(5);
System.out.println(dfsIterative(1, graph)); // [1, 2, 4, 3, 5]
}
}graph = [
[],
[2, 3],
[4],
[5],
[],
[],
]
def dfs_iterative(start):
visited = [False] * 6
stack = [start]
order = []
while stack:
node = stack.pop()
if visited[node]:
continue
visited[node] = True
order.append(node)
for nxt in reversed(graph[node]):
if nxt not in visited:
stack.append(nxt)
return order
print(dfs_iterative(1)) # [1, 2, 4, 3, 5]fn dfs_iterative(start: usize, graph: &Vec<Vec<usize>>) -> Vec<usize> {
let mut visited: Vec<bool> = vec![false; 6];
let mut stack: Vec<usize> = vec![start];
let mut order: Vec<usize> = Vec::new();
while let Some(node) = stack.pop() {
if visited[node] {
continue;
}
visited[node] = true;
order.push(node);
let nexts = &graph[node];
let mut i = nexts.len();
while i > 0 {
i -= 1;
let nxt = nexts[i];
if !visited[nxt] {
stack.push(nxt);
}
}
}
order
}
fn main() {
let graph: Vec<Vec<usize>> = vec![
vec![],
vec![2, 3],
vec![4],
vec![5],
vec![],
vec![],
];
println!("{:?}", dfs_iterative(1, &graph));
}재귀/반복 전개 결과 전개 흐름 추적
반복 구현은 호출 스택 대신 명시적 스택을 사용합니다.
깊은 입력에서도 재귀 제한에 덜 민감하고, 상태를 눈으로 추적하기 쉽습니다.
대신 push/pop 순서를 잘못 설계하면 방문 순서가 바뀌거나 누락될 수 있습니다.
- 평균 시간복잡도:
O(V + E) - 최악 시간복잡도:
O(V + E) - 공간복잡도:
O(V)(방문 집합 + 명시적 스택)
재귀 깊이/반복 횟수 입력 분포 기준
문제에서 다음 항목을 우선 확인하면 선택이 쉬워집니다.
- 재귀 깊이가 커질 가능성이 있는가
- 호출 구조가 매우 단순해 재귀 표현 이점이 큰가
- 디버깅 시 상태를 단계별로 확인해야 하는가
- 팀 코딩 스타일이 재귀/반복 중 무엇에 익숙한가
알고리즘보다 운영 환경 제약이 선택을 결정하는 경우가 많습니다.
호출 스택과 코드 가독성 상충 지점
재귀와 반복의 균형점은 다음과 같습니다.
- 재귀: 코드가 짧고 선언적이지만 스택 제한에 취약
- 반복: 제어가 명시적이고 안전하지만 코드가 길어질 수 있음
- 재귀 + 메모이제이션: 구현은 간결하지만 캐시 전략 설계가 필요
짧은 코드와 안전한 실행 중 우선순위를 문제 맥락에 맞춰 정해야 합니다.
전개 순서 오답 패턴과 교정 방법
다음 케이스에서 오류가 자주 발생합니다.
- 재귀 종료 조건 누락으로 무한 호출
- 반복 구현에서 방문 체크 시점이 늦어 중복 push 폭증
- 그래프가 순환 구조인데 트리처럼 가정하고 구현
- 전역 상태를 재사용해 여러 테스트 케이스가 오염
같은 알고리즘이라도 상태 저장 방식이 다르면 버그 양상이 달라집니다.
팩토리얼을 통한 상태 전개 비교
문제 의도: 동일 문제를 재귀/반복으로 풀어 상태 저장 방식 차이를 단순하게 비교합니다.
입력 예시: n=5
출력 예시: 120, 120
동일한 수학 문제를 재귀/반복으로 구현하면 상태 저장 차이가 더 선명하게 보입니다.
#include <iostream>
using namespace std;
long long factorialRecursive(int n) {
if (n <= 1) return 1;
return static_cast<long long>(n) * factorialRecursive(n - 1);
}
long long factorialIterative(int n) {
long long result = 1;
for (int x = 2; x <= n; ++x) result *= x;
return result;
}
int main() {
cout << factorialRecursive(5) << "\n";
cout << factorialIterative(5) << "\n";
return 0;
}public class Main {
static long factorialRecursive(int n) {
if (n <= 1) return 1;
return (long) n * factorialRecursive(n - 1);
}
static long factorialIterative(int n) {
long result = 1;
for (int x = 2; x <= n; x++) result *= x;
return result;
}
public static void main(String[] args) {
System.out.println(factorialRecursive(5));
System.out.println(factorialIterative(5));
}
}def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n - 1)
def factorial_iterative(n):
result = 1
for x in range(2, n + 1):
result *= x
return result
print(factorial_recursive(5)) # 120
print(factorial_iterative(5)) # 120fn factorial_recursive(n: u64) -> u64 {
if n <= 1 {
1
} else {
n * factorial_recursive(n - 1)
}
}
fn factorial_iterative(n: u64) -> u64 {
let mut result = 1u64;
for x in 2..=n {
result *= x;
}
result
}
fn main() {
println!("{}", factorial_recursive(5));
println!("{}", factorial_iterative(5));
}재귀/반복 전개 결과 재확인
재귀 버전은 호출 스택이 n, n-1, ... 상태를 자동으로 보관합니다.
반복 버전은 result 변수 하나로 누적 상태를 직접 관리합니다.
둘의 정답은 같지만 메모리 사용 방식과 디버깅 포인트는 다릅니다.
깊이가 매우 커질 수 있는 문제라면 반복이 더 안전한 경우가 많습니다.
반대로 문제 정의 자체가 트리 구조라면 재귀 표현이 더 직관적일 수 있습니다.
- 평균 시간복잡도: 재귀/반복 모두
O(N) - 최악 시간복잡도: 재귀/반복 모두
O(N) - 공간복잡도: 재귀
O(N), 반복O(1)
접근 실수 방지 가이드
재귀/반복 선택 전에 아래를 확인하면 실패가 줄어듭니다.
- 최대 깊이 추정치가 언어 스택 한계를 넘는가
- 상태 복원이 필요한가, 단순 누적인가
- 호출 경로를 로깅해야 하는가
- 팀원이 유지보수하기 쉬운 형태인가
이 질문을 무시하면 맞는 코드를 만들고도 운영 단계에서 장애를 만날 수 있습니다.
종료 조건 누락 실패사례 확인 포인트
- 파이썬 재귀 한계(
recursionlimit)를 무시하면 큰 입력에서 실패합니다. - 반복 구현에서 스택 삽입 순서를 바꾸면 결과 순서가 달라질 수 있습니다.
- 방문 배열/집합 초기화를 테스트 케이스마다 분리해야 합니다.
- 성능 측정 시 I/O 비용을 알고리즘 비용과 혼동하지 않습니다.
스택 깊이와 입력 분포 판단
같은 정답이라도 입력 분포에 따라 병목 지점이 달라지므로, 판단 축을 시간복잡도 표 하나로 끝내지 말고 분포 가정까지 명시해야 합니다.
| 방식 | 평균 시간 | 최악 시간 | 공간 |
|---|---|---|---|
| 재귀 DFS | O(V+E) | O(V+E) | O(V) |
| 반복 DFS | O(V+E) | O(V+E) | O(V) |
차이는 복잡도보다 안정성과 디버깅 편의성에서 드러납니다.
제출 직전 전개 검증 체크리스트
- 최대 재귀 깊이를 입력 제약으로 계산했는가
- 종료 조건과 방문 체크 시점을 코드에 명확히 뒀는가
- 재귀/반복 중 운영 환경에 더 안전한 방식을 선택했는가
- 순회 결과 순서가 요구사항과 일치하는지 검증했는가
재귀와 반복 선택 정리
재귀와 반복은 우열 관계가 아니라 표현 전략의 차이입니다.
상태 전개를 우선 정의하고 표현 방식을 고르면, 정답률과 유지보수성이 함께 올라갑니다.