재귀와 반복 저장 위치

종료 조건을 먼저 둔다

재귀가 멈추는 입력 크기와 반환값을 명확히 하지 않으면 무한 호출이 된다.

인자로 넘길 값, 전역으로 둘 값, 반환으로 받을 값을 분리한다.

입력 크기가 크면 재귀 깊이가 제한을 넘을 수 있어 반복 변환이 필요하다.

Recursion

문제 구조가 보임 트리, DFS, 분할 정복처럼 자기 닮은 구조에 잘 맞는다.

깊이 제한을 확인한다.

Iteration

수명과 비용이 명시적 루프 변수와 자료구조가 드러나 메모리 제어가 쉽다.

상태 갱신 순서가 중요하다.

Memo

중복 호출 제거 같은 상태를 다시 계산하지 않도록 결과를 저장한다.

상태 키가 정확해야 한다.

Tail

끝 호출 형태 C++은 tail call 최적화를 보장하지 않는다.

깊으면 반복을 고려한다.

종료 모든 경로가 base case에 도달하는가.

중복 같은 상태가 여러 번 계산된다면 memoization이 필요한가.

깊이 최악 입력에서 호출 스택이 터지지 않는가.

// dfs(v): visited[v] = true
// for next in graph[v]: if !visited[next] dfs(next)
// 반복 버전은 call stack을 vector<int> stack으로 바꾼다.