"재귀가 무엇을 치르는지 알고 싶으면 호출을 트리로 그려 봐. 트리의 모양, 그러니까 얼마나 넓게 갈라지고 얼마나 깊이 내려가는지가 곧 복잡도야. 그리고 같은 가지를 계속 다시 계산하는 트리는 손쉬운 속도를 그냥 흘려보내고 있다는, 알고리즘에서 가장 큰 신호고."
재귀는 트리를 만들어
모든 재귀 계산은 재귀 트리를 그려 내. 루트는 원래 호출이고, 그 자식은 그 호출이 만드는 호출이고, 또 그 자식은 그것들이 만드는 호출이고, 리프에 base case가 놓여. 비용을 분석하려면 이 트리를 읽으면 돼. 노드 하나가 자식을 몇 개 낳는지(분기), 문제가 얼마나 빨리 줄어드는지(깊이), 노드마다 일이 얼마나 되는지. 이걸 곱하면 복잡도가 나와. 트리가 '이 재귀 비싼가?'라는 물음을 신비에서 그림으로 바꿔 주는 거야.
피보나치 재앙
순진한 재귀 피보나치 fib(n) = fib(n−1) + fib(n−2)의 호출 수는 Θ(φⁿ)이고 O(2ⁿ)로도 상한을 잡을 수 있어. 아래 코드처럼 base 호출까지 세면 fib(40)이 약 3억 3천만 호출로 10억 아래야. 그런데 정확한 숫자보다 중요한 건 구조야. fib(3) 같은 똑같은 상태를 계속 다시 계산하면서 지수적으로 부풀어 오른다는 것.
트리 가지치기: DP 신호
다음 트랙 전체를 세워 주는 보상이 여기 있어. fib(k)를 처음 계산할 때마다 dict에 기억해 두면, 나중에 같은 걸 물을 때 서브트리를 다시 계산하는 대신 즉시 조회로 끝나. 뚱뚱하던 지수 트리가 고유한 계산 n개짜리 얇은 선으로 주저앉는 거야. 캐싱 하나로 O(2ⁿ)이 O(n)이 돼. 이게 메모이제이션이고, '내 재귀 트리가 같은 부분 문제를 다시 계산하고 있네'라는 인식이 동적 계획법이 적용된다는 가장 큰 단일 신호야. 재귀 트리를 그려서 반복되는 서브트리가 보이면 공짜 속도를 찾은 거지.
모든 트리가 뚱뚱한 건 아니야
분기 자체가 나쁜 건 아니야. 충분히 안 줄어들면서 분기할 때 폭발하는 거지. 병합 정렬도 두 갈래로 갈라지지만 호출마다 데이터의 절반을 다루니까 트리가 log n 깊이밖에 안 되고, 단계마다 총 O(n)이라 전체가 O(n log n)이야. 아무 문제 없지. 차이는 줄어드는 속도에 있어. 절반씩 줄이면(병합 정렬) 트리가 짧아지고, 상수만큼만 줄면서 분기하면(피보나치) 지수가 돼. master theorem이 분할 정복에서 이 분기 대 축소 분석을 공식으로 정리해 주는데, 직관은 트리를 그리는 쪽이 먼저 줘.
피파의 고백
fib(45)가 터미널을 멈춰 세웠고, 나는 진짜 무한 루프를 짠 줄 알았어. 아빠가 fib(5)의 호출 트리를 종이에 그려 보라고 했지. 그랬더니 거기 fib(2)가 다섯 번이나 따로 계산되고 있더라. 그리는 순간 중복이 눈에 보였어. 결과를 캐시하는 dict 하나를 넣으니 fib(45)가 즉시 반환했고. 그 뒤로 재귀가 느리게 느껴질 때마다 트리를 그려. 반복되는 서브트리가 종이에서 툭 튀어나와서 낭비되는 일이 정확히 어디인지 보여주거든.