base case 또는 while 조건
state storage
재귀와 반복은 같은 상태를 다른 위치에 저장한다
종료 조건, 현재 위치, 방문 정보, 다음 후보가 어디에 저장되는지 보이면 재귀와 반복 변환이 쉬워진다.
재귀
반복
상태 저장 위치 지도
함수 인자 또는 loop 변수
호출 순서 또는 stack push 순서
중복 호출을 막는 visited
| 상태 | 재귀에서 저장되는 곳 | 반복으로 바꿀 때 |
|---|---|---|
| 현재 노드 | dfs(v)의 인자 v | stack에서 꺼낸 값 cur |
| 복귀 위치 | 호출 스택의 다음 실행 지점 | 명시 stack에 다음 후보를 push |
| 중복 방지 | 방문 전후에 visited를 갱신 | push 시점 또는 pop 시점 중 하나로 통일 |
| 깊이 위험 | 깊은 입력에서 스택 초과 | 컨테이너 크기를 코드에서 관리 |