재귀 트리: 비용을 보기

"재귀가 뭘 치르는지 알려면, 호출의 트리로 그려. 트리의 모양 — 얼마나 넓게 갈라지고, 얼마나 깊이 가는지 — 이 곧 복잡도야. 그리고 같은 가지를 계속 다시 계산하는 트리가, 쉬운 속도를 테이블에 남기고 있다는 알고리즘에서 가장 큰 신호야."

재귀는 트리를 만든다

모든 재귀 계산이 재귀 트리를 그려내: 루트는 원래 호출, 그 자식은 그게 하는 호출, 그 자식은 그것들이 하는 호출, 리프의 base case 까지. 비용을 분석하려면, 트리를 읽어: 각 노드가 자식을 몇 개 낳고 (분기), 문제가 얼마나 빨리 줄고 (깊이), 각 노드에 일이 얼마? 곱해내면 복잡도야. 트리가 '이 재귀가 얼마나 비싸?' 를 신비에서 그림으로 바꿔.

피보나치 재앙

가장 유명한 경고 이야기: 순진한 재귀 피보나치, fib(n) = fib(n−1) + fib(n−2). 그 트리를 그려 — 각 호출이 거의 안 주는 (1 이랑 2 만큼) 자식 둘을 낳아, 그래서 트리가 거대하고 무성해: 약 2ⁿ 노드. fib(40) 이 십억 넘는 호출을 해. 더 나쁘게, 자세히 보면 같은 값이 계속 계산되는 걸 봐 — fib(3) 이 수십 군데 나타나, 매번 처음부터 다시 계산. 트리가 중복 일로 살쪄. 그 중복이 재앙이야: 자명해야 할 것에 지수 알고리즘.

트리 가지치기: DP 신호

다음 트랙 전체를 세우는 보상이야. 각 fib(k) 를 처음 계산할 때 기억하면 (dict 에), 나중 모든 요청이 다시 계산된 서브트리 대신 즉시 조회야. 살찐 지수 트리가 n 개 고유 계산의 얇은 선으로 무너져 — 캐싱만으로 O(2ⁿ) 가 O(n) 이 돼. 이게 메모이제이션 이고, '내 재귀 트리가 같은 부분 문제를 다시 계산해' 라는 인식이 동적 계획법 (다음 트랙) 이 적용된다는 단 하나의 가장 큰 신호야. 재귀 트리를 그리고 반복된 서브트리를 보면, 공짜 속도를 찾은 거야.

모든 트리가 살찐 건 아니야

분기가 자동으로 나쁜 게 아니야 — 충분히 안 줄면서 분기하는 게 폭발해. 병합 정렬도 두 갈래 분기지만, 각 호출이 데이터 절반에 일해, 그래서 트리가 log n 깊이뿐이고 각 레벨 총 O(n) 일 → O(n log n), 완벽히 괜찮아. 차이는 줄이는 속도: 절반 내기 (병합 정렬) 는 짧은 트리; 상수만큼 줄면서 분기 (피보나치) 는 지수. master theorem 이 분할 정복의 이 분기-대-줄이기 분석을 형식화해 — 근데 트리를 그리는 게 직관을 먼저 줘.

피파의 고백