從遞迴程式碼到遞迴關係式

為什麼遞迴程式碼需要遞迴的成本

到目前為止，你已經會數一個迴圈的成本：走過迴圈主體、看它跑幾次、相乘即可。但遞迴程序拒絕被這樣數，因為它在做事做到一半時，會對一個更小的輸入呼叫「自己」，而你還不知道那要花多少。誠實的做法不是假裝知道，而是給這個未知數取個名字。令 T(n) 代表在一個規模為 n 的輸入上的執行時間——正是我們想求的東西——然後寫下一條 T 必須滿足的方程式。這條方程式就是遞迴關係式：用 T 在更小引數上的值來描述 T(n)。

這不是循環論證的耍賴；它和我們證明正確性時所用的對遞迴呼叫做歸納是同一個招式，只是現在拿來算成本。在那裡，我們假設遞迴呼叫對更小的輸入回傳正確答案，只檢查它周圍的銜接。在這裡，我們假設遞迴呼叫恰好花 T（它那個更小的規模），只去數當前這層呼叫自己額外做的工作。求解這條遞迴關係式——正是接下來四篇導覽的任務——才終於把這個被命名的未知數，化成一個乾淨的大 O 符號。

直接從程式碼讀出方程式

這裡有個機械式的步驟，而它永遠有兩個部分。第一，找出程序所發出的每一個遞迴呼叫，並記下每個呼叫的輸入有多大——這給出右側的 T(...) 各項。第二，數出一次呼叫中所有「非遞迴」的工作：分割、合併、比較，以及在呼叫之前或之後跑的迴圈。這份非遞迴的工作，寫成 n 的函數，通常記作 f(n)。把它們黏在一起，就得到 T(n) =（呼叫各項）+ f(n)。本節全部的功夫，就是把這兩部分分清楚、不要重複計數。

掃描主體找出對自己的呼叫。數出有幾個、每個的輸入規模是多少——例如對兩半各一次呼叫，或對 n-1 的一次呼叫。
把這一層呼叫中的非遞迴工作加總成 n 的函數；那就是 f(n)（常見是 Theta(1)、Theta(n) 或 Theta(n^2)）。
寫下 T(n) =（各呼叫規模的 T 之和）+ f(n)——這是遞迴情況，僅在 n 夠大時成立。
另外寫下基底情況：在程式碼停止遞迴的最小規模上釘住 T，例如 T(1) = Theta(1)。

把這個步驟套到合併排序上。它發出兩個遞迴呼叫、各對陣列的一半，所以呼叫各項是 T(n/2) + T(n/2) = 2 T(n/2)。唯一的非遞迴工作是把兩個有序半邊做線性時間的合併，所以 f(n) = Theta(n)。這就得到分治遞迴關係式 T(n) = 2 T(n/2) + Theta(n)——正是我們數合併排序時遇到的那條方程式，只是現在是推導出來的，而非直接塞給你。二分搜尋讀起來同樣乾淨：一個呼叫對陣列的一半、加上 Theta(1) 的工作去選邊，得到 T(n) = T(n/2) + Theta(1)。

a、b、f(n) 的格式，以及它在哪裡失效

許多分治演算法會產生一種整齊格式的遞迴關係式：T(n) = a T(n/b) + f(n)，把這三個旋鈕讀出聲來很值得。這裡 a 是你製造出幾個子問題，b 是每個子問題縮小的倍率，而 f(n) 是分割輸入與合併答案的工作。合併排序是 a=2、b=2、f(n)=Theta(n)。著名的卡拉楚巴乘法把樸素的 a=4 變成 a=3、b=2、f(n)=Theta(n)，而光是這從 4 降到 3 的一步，就是它勝過小學乘法的全部原因。認得出 a、b、f，正是讓主定理得以發動的關鍵。

T(n) = a * T(n/b) + f(n)
         |        |       |
         |        |       +--- work OUTSIDE the recursive calls (split + combine)
         |        +----------- each subproblem is 1/b the size
         +-------------------- number of recursive calls

  merge sort   : a=2, b=2, f(n)=Theta(n)
  binary search: a=1, b=2, f(n)=Theta(1)
  Karatsuba    : a=3, b=2, f(n)=Theta(n)

主定理專為求解而生的 a／b／f(n) 範本，以及讀進其中的三個熟悉演算法。

不過要誠實：不是每個遞迴都套得進這個模子，而假裝它套得進，正是初學者最常踏的陷阱。有些演算法切得「不均」——快速排序在最壞情況下，剝掉一個元素、對 n-1 遞迴，給出 T(n) = T(n-1) + Theta(n)，這是一條每次減一的遞迴關係式，而非除以 b 的那種。另一些則切成「不同」大小的片段，像 T(n) = T(n/3) + T(2n/3) + Theta(n)；這些就是樸素主定理根本碰不了的不均切割遞迴關係式，我們將需要 Akra-Bazzi 方法來對付它們。把遞迴關係式寫對，正是揭示你被允許使用哪個工具的方式。

別忘了基底情況

一條只有遞迴那一行的遞迴關係式，是一個沒有句點的句子。遞迴情況 T(n) = 2 T(n/2) + Theta(n) 描述的是大型輸入，但在你說出遞迴在哪裡觸底之前，它毫無意義。那就是基底情況：程式碼直接處理的最小輸入，幾乎總是用常數量的工作，寫成 T(1) = Theta(1)（或對某個小門檻以下的 n 寫成 T(n) = Theta(1)）。少了它，T 是真的沒有定義的——而實際程式裡的遞迴也將永遠停不下來。

四種求解方式——本階的地圖

遞迴關係式一旦寫好，目標就是一個封閉形式的大O符號。對此並沒有單一的按鈕，而前方的四篇導覽是四個真正不同的工具——值得先預覽，好讓你知道自己在伸手抓什麼。遞迴樹法把呼叫畫成一棵分岔的樹，計算每一層的工作，再沿層相加；它最直觀，也最適合建立「時間花在哪裡」的直覺。代入法是嚴謹的骨幹：你先猜出答案，再用歸納法證明它，是四者中唯一能給出滴水不漏的證明、而非自信估計的。

第三個工具是壓軸主角。主定理是針對 T(n) = a T(n/b) + f(n) 這個格式的一張查表：把 f(n) 與基準 n 的臨界指數 log 以 b 為底 a 次方相比，三種情況中的一種就會把答案交給你，完全不用畫樹。它快，而且涵蓋了極大一塊分治演算法——但要看清楚：它只解這個格式，有附帶細則（其中一個情況有正則性條件），而且它刻意忽略其餘的情形。第四篇導覽 Akra-Bazzi，正是把主定理晾在一旁的那些不均、多項遞迴關係式救回來的推廣。