從方程式到圖像
上一篇導覽教我們讀懂遞迴程式碼並 寫出它的遞迴關係式——像 T(n) = 2 T(n/2) + cn 這樣的方程式，它說的是「規模 n 的成本，等於那些遞迴呼叫的成本，加上這一次呼叫自己所做的工作」。這條方程式是對的，卻沉默：它不會自己宣告答案。遞迴樹法 是讓它開口最直觀的方式。想法簡單又視覺化：把遞迴關係式展開成它所描述的實際呼叫樹，為每個節點標上它在本地所做的工作，然後把一切加總。你在這裡並沒有發明新的數學——你只是在小心地記帳。
整套作法一口氣講完。樹根是規模 n 的原始呼叫；它的子節點是它衍生出的子問題；子節點的子節點是子子問題，如此一路往下，直到葉子處的基底情況。在每個節點上只寫 本地成本——遞迴關係式裡的 f(n) 部分，也就是該節點在它的遞迴呼叫之外所做的工作，絕不把它的後代算進去。接著按 層 把節點分組（同一深度的所有節點），求出每一層的總工作量，再跨層相加。這個總和就是 T(n)。功夫幾乎全在兩個問題上：一層上坐著多少工作量，以及一共有幾層？
合併排序樹，一層一層看
拿標準的 分治遞迴關係式 T(n) = 2 T(n/2) + cn，也就是 合併排序 產生的那條。樹根做 cn 的工作，有兩個子節點，各是規模 n/2、做 c(n/2) 工作的問題。那四個孫節點各是規模 n/4、做 c(n/4) 工作——而規律已經清楚了。在深度 k，有 2^k 個節點，每個規模 n/2^k，每個做 c·(n/2^k) 的工作。把個數乘上每節點成本：該層總和為 2^k · c·(n/2^k) = cn。每一層恰好都做 cn 的工作。這份平衡正是答案的核心。
T(n) = 2 T(n/2) + c*n
depth nodes size each work each LEVEL TOTAL
0 1 n c*n c*n
1 2 n/2 c*n/2 c*n
2 4 n/4 c*n/4 c*n
... ... ... ... ...
log n n 1 c c*n
-------------
levels = log2(n) + 1, each c*n -> c*n*(log n + 1) = O(n log n)現在來看第二個問題：有幾層？每往下一步就把規模除以 2，所以 k 層之後規模是 n/2^k。遞迴在規模降到 基底情況 的 1 時停止，也就是 n/2^k = 1，這表示 k = log2(n)。把樹根算進去，就是 log2(n) + 1 層。約 log n 層、每層 cn 工作，總和為 cn · (log n + 1) = Theta(n log n)。注意這張圖是在「解釋」答案，而非僅僅「斷言」它：那個 n 來自鋪在每一層上的工作量，而那個 log n 來自樹的高度——把 n 反覆減半到撞上 1 為止的次數。
當各層並不平衡時
合併排序是容易的情形，因為每一層成本都相同。而遞迴樹真正派上用場，恰恰是在各層不相同的時候。考慮 T(n) = 2 T(n/2) + c（每次呼叫做常數工作，而非線性）。同樣的分枝、同樣的高度：深度 k 有 2^k 個節點，但現在每個只做 c 的工作，所以該層總和是 2^k · c——它每往下一層就翻倍，而不是維持平坦。光是最底層就有約 n 個節點、各做 c，貢獻 cn，把上面所有層都比了下去。把這個倍增級數加起來，總和由最後一層主導：Theta(n)。葉子贏了。
現在反過來：T(n) = 2 T(n/2) + c·n^2。每一層的總和是 2^k · c·(n/2^k)^2 = c·n^2 / 2^k——它每往下一層就減半，而非倍增，是一個遞減的幾何級數。光樹根就做 c·n^2，而它底下的一切加起來至多再多一個 c·n^2（公比 1/2 的幾何級數，總和是首項的兩倍）。所以總和是 Theta(n^2)：樹根主導，葉子可忽略。三條遞迴、形狀相同、三個不同的故事——平衡的（n log n）、頭輕腳重的（n）、頭重腳輕的（n^2）——而遞迴樹一眼就讓你看出是哪一種，只看各層總和是維持平坦、向下增長、還是向下萎縮。
枝椏不齊的樹
這個方法不需要乾淨的減半。拿 T(n) = T(n/3) + T(2n/3) + cn，它出現在切割不對稱的時候。兩個子節點以不同速率縮小，所以樹是不平衡的：n/3 那一枝約 log_3(n) 層後到達葉子，而 2n/3 那一枝會一路撐到約 log_{3/2}(n) 層。儘管如此，這裡有個救命之處——每一個完整層的工作量至多 cn，因為一層上所有節點的規模總和永遠是 n（每一單位的原始輸入都被分配給它們、絕不重複）。各層總和維持在 cn，直到有些枝椏開始觸底。
所以總和是 cn 乘以高度，而高度由縮得最慢的那一枝決定：最長的路徑反覆乘以 2/3，約 log_{3/2}(n) 層後到達 1。這使得總和又是 Theta(n log n)——和平衡切割一樣的答案，只是對數底裡藏了不同的常數。這正是遞迴樹做到了 主定理 做不到的事：主定理要求子問題等大（a 份規模 n/b），而像這樣不均的切割落在它的形式之外。遞迴樹直接處理它，而本級最後一篇所介紹的 Akra-Bazzi 方法，正是把這種不均加總自動化的通用機制。
一個猜測，還不是證明
這裡是讓遞迴樹保持謙遜的誠實警語。畫它通常牽涉一點手法：我們假設 n 是 b 的完全冪次（2 的冪、3 的冪等等），好讓各層出落乾淨；我們把每層的和當成精確值處理；而我們對幾何級數揮揮手帶過，而非逐項加以界定。這些捷徑用來「找出答案」沒問題，但它們不是證明。真實的遞迴帶有向下與向上取整——T(floor(n/2)) 與 T(ceil(n/2))——而一棵為整齊冪次所畫的樹，本身並不能擔保那個雜亂的一般情形。
這正是為什麼遞迴樹與下一篇的方法是夥伴、而非對手。用樹產生一個有信心的 猜測——「這看起來像 Theta(n log n)」——再把那個猜測交給代入法，它以 猜測並驗證 搭配 歸納法，證出一個對所有 n（含向下與向上取整）都成立的乾淨界。在你信任一個由樹得來的猜測之前，有個好用的健全性檢查：若各層總和構成幾何級數，答案就是主導的那一端（樹根，或葉子數乘以每片成本）；若它們是平坦的，就把一層的成本乘以層數。從樹得到定性的形狀；從代入法取得那張證書。