dfs(1)
dfs(2)
dfs(5)
현재 노드, 다음 이웃, 복귀 위치가 호출 프레임에 숨어 있다.
state expansion
재귀와 반복은 상태를 저장하는 위치가 다르다
같은 DFS라도 재귀는 호출 스택에 상태를 맡기고, 반복은 명시 스택과 방문 배열로 상태를 직접 관리한다.
call stack
explicit stack
같은 탐색 상태의 두 표현
stack: [1, 2, 5]
visited: {1, 2, 5}
next index: 직접 갱신
상태를 자료구조에 꺼내 놓으므로 깊이 제한과 순서를 제어하기 쉽다.
| 판단 기준 | 재귀가 자연스러운 경우 | 반복이 안전한 경우 |
|---|---|---|
| 문제 구조 | 트리, 분할 정복처럼 하위 문제가 같은 모양 | 상태 전이가 길고 스택 깊이가 커질 수 있음 |
| 종료 조건 | base case를 한 줄로 설명 가능 | 중간 중단, 재시작, 순서 제어가 필요 |
| 위험 신호 | base가 없으면 무한 호출 | visited나 push 순서가 빠지면 중복 방문 |