A loop within a loop;
A pointer to a pointer;
A recursion within a recursion;
《The C Programming Language》一書之所以被列為經典，不僅在於這是 C 語言發明者的著作，更在於不到三百頁卻涵蓋 C 語言的精髓，佐以大量範例，循序漸進。更奇妙的是，連索引頁 (index) 也能隱藏學問。
上圖是《The C Programming Language》的第 269 頁，是索引頁面的一部分，注意到 recursion (遞歸)一字出現在書本的第 86, 139, 141, 182, 202, 以及 269 頁，後者恰好就是 recursion 出現的頁碼，符合遞歸定義！
遞歸讓你直覺地表示特定模式
觀賞影片 Binary, Hanoi and Sierpinski - Part I 和 Binary, Hanoi, and Sierpinski - Part II，記得開啟的字幕(這兩個鏈接無法訪問)
電腦程序中，子程式直接或間接調用自己就稱為遞歸。遞歸算不上演算法，只是程序流程控制的一種。程序的執行流程只有兩種:
- 循序，分支(循環)
- 調用子程序(遞歸)
循環是一種特別的分支，而遞歸是一種特別的子程序調用。
不少初學者以及教初學者的人把遞歸當成是複雜的演算法，其實單純的遞歸只是另一種函數定義方式而已，在程序指令上非常簡單。初學者為什麼覺得遞歸很難呢？因為他跟人類的思考模式不同，電腦的兩種思維模式：窮舉與遞歸(enumeration and recursion)，窮舉是我們熟悉的而遞歸是陌生的，而遞歸為何重要呢？因為他是思考好的演算法的起點，例如分治與動態規劃。
- 分治：一刀均分左右，兩邊各自遞歸，返回重逢之日，真相合並之時。
分治 (Divide and Conquer) 是種運用遞歸的特性來設計演算法的策略。對於求某問題在輸入 S 的解 P(S) 時，我們先將 S 分割成兩個子集合 S1 與 S2，分別求其解 P(S1) 與 P(S2)，然後再將其合併得到最後的解 P(S)。要如何計算 P(S1) 與 P(S2) 呢？因為是相同問題較小的輸入，所以用遞歸來做就可以了。分治不一定要分成兩個，也可以分成多個，但多數都是分成兩個。那為什麼要均分呢？從下面的舉例說明中會了解。
從一個非常簡單例子來看：在一個數組中如何找到最大值。循環的思考模式是：從前往後一個一個看，永遠記錄著目前看到的最大值。
<code>m = a[0];
for (i = 1 ; i < n; i++)
m = max(m, a[i]);/<code>
分治思考模式：如果我們把數組在 i 的位置分成前後兩段 a[0,i−1] 與a[i,n]，分別求最大值，再返回兩者較大者。切在哪裡呢？如果切在最後一個的位置，因為右邊只剩一個無須遞歸，那麼會是
<code>int find_m1(int n) {
if (n == 0) return a[0];
return max(find_m1(n - 1), a[n]);
}/<code>這是個尾端遞歸(Tail Recursion)，在有編譯最佳化的狀況下可跑很快，其實可發現程序的行為就是上面那個循環的版本。若我們將程序切在中點:
<code>int find_m2(int left, int right) { // 範圍=[left, right) 用左閉右開區間
if (right - left == 1) return a[left];
int mid = (left + right) / 2 ;
return max(find_max(left, mid), find_max(mid, right);
}/<code>效率一樣是線性時間，會不會遞歸到 stack overflow 呢？放心，如果有200 層遞歸數組可以跑到 2的200次方，地球已毀滅。
再來看個有趣的問題：假設我們有一個程序比賽的排名清單，有些選手是女生有些是男生，我們想要計算有多少對女男的配對是男生排在女生前面的。若以 0 與 1 分別代表女生與男生，那麼我們有一個 0/1 序列 a[n]，要計算
<code>Ans = | {(a[i], a[j]) | i < j 且 a[i] > a[j]} |
/<code>循環的思考方式：對於每一個女生，計算排在他前面的男生數，然後把它全部加起來就是答案。
<code>for (i = 0, ans = 0 ; i < n ;i++) {
if (a[i]==0) {
cnt = num of 1 before a[i];
ans += cnt;
}
}/<code>效率取決於如何計算 cnt。如果每次拉一個循環來重算，時間會跑到 O(n2)，如果利用類似前綴和 (prefix-sum) 的概念，只需要線性時間。
<code>for (i = 0, cnt = 0, ans = 0 ; i <n ;i++) {
if (a[i] == 0)
ans += cnt;
else cnt++;
}/<code>接下來看分治思考模式。如果我們把序列在 i 處分成前後兩段 a[0,i−1] 與 a[i,n]，任何一個要找的 (1, 0) 數對只可能有三個可能：都在左邊、都在右邊、或是一左一右。所以我們可左右分別遞歸求，對於一左一右的情形，我們若知道左邊有 x 個 1 以及右邊有 y 個 0，那答案就有 xy 個。遞歸終止條件是什麼呢？剩一個就不必找下去。
<code>int dc(int left, int right) { // 範圍=[left,right) 慣用左閉右開區間
if (right - left < 2) return 0;
int mid = (left + right) / 2; // 均勻分割
int w = dc(left, mid) + dc(mid, right);
\t計算x = 左邊幾個 1, y = 右邊幾個 0
return w + x * y;
}/<code>時間複雜度呢？假設把範圍內的數據重新看一遍去計算 0 與 1 的數量，那需要線性時間，整個程序的時間變成 T(n)=2T(n/2)+O(n)，結果是 O(nlogn)，不好。比循環的方法差，原因是因為我們計算 0/1 的數量是重複計算。我們讓遞歸也回傳 0 與 1 的個數，效率就會改善了，用 Python 改寫：
<code>def dc(left, right):
if right - left == 1:
if ar[left]==0: return 0, 1, 0 # 逆序數，0的數量，1的數量
return 0, 0, 1
mid = (left + right) // 2 #整數除法
w1, y1, x1 = dc(left,mid)
w2, y2, x2 = dc(mid,right)
return w1 + w2 + x1 * y2, y1 + y2, x1 + x2/<code>
時間效率是 T(n)=2T(n/2)+O(1)，所以結果是 O(n)。
如果分治可以做的循環也可以，那又何必學分治？第一，複雜的問題不容易用循環的思考找到答案；第二，有些問題循環很難做到跟分治一樣的效率。上述男女對的問題其實是逆序數對問題的弱化版本：給一個數字序列，計算有多少逆序對，也就是
<code>| {(a[i], a[j]) | i < j 且 a[i] > a[j]} |。
/<code>循環的思考模式一樣去算每一個數字前方有多少大於它的數，直接做又搞到O(n^2)，有沒有辦法像上面男女對問題一樣，記錄一些簡單的數據來減少計算量呢？你或許想用二分查找，但問題是需要重排序，就我所知，除非搞個複雜的數據結構，否則沒有簡單的辦法可以來加速。那麼來看看分治。基本上的想法是從中間切割成兩段，各自遞歸計算逆序數並且各自排序好，排序的目的是讓合併時，對於每個左邊的元素可以笨笨地運用二分查找去算右邊有幾個小於它。
<code>LL sol(int le, int ri) { // 區間 = [le,ri)
if (ri-le == 1) return 0;
int mid = (ri + le) / 2;
LL w = sol(le, mid) + sol(mid, ri);
LL t = 0;
for (int i = le; i < mid; i++)
t += lower_bound(ar + mid, ar + ri, ar[i]) - (ar + mid);
sort(ar + le, ar + ri);
return w + t;
}/<code>時間複雜度呢？即使我們笨笨地把兩個排好序的序列再整個重排，T(n)=2T(n/2)+O(nlogn)，結果是O(nlog 2 (n))，十萬筆數據不需要一秒，比循環的方法好多了。為什麼說笨笨地二分查找與笨笨地重新排序呢？對於兩個排好序的東西要合併其實可以用線性時間。那二分查找呢？沿路那麼多個二分查找其實可以維護兩個註標一路向右就好了。所以事實上不需要複雜的數據結構可以做到O(nlogn)，熟悉演算法的人其實看得出來，這個方法基本上就是很有名的merge sort，跟quick sort 一樣常拿來當作分治的範例。另外，如果merge sort的分割方式如果是[left,right−1][left,right−1] [right−1,right][right−1,right]，右邊只留一個，那就退化成insertion sort 的尾端遞迴。
注：計算遞歸的時間需要解遞歸函數，這是有點複雜的事情。好在大多數常見的有公式解。
Tail recursion 是遞歸的一種特殊形式，子程序只有在最後一個動作才調用自己。以演算法的角度來說，recursion tree 全部是一脈單傳，所以間複雜度是線性個該子程序的時間。不過遞歸是需要系統使用stack 來儲存某些數據，於是還是會有stack overflow 的問題。但是從編譯器的角度來說，因為最後一個動作才調用遞歸，所以很多stack 數據是沒用的，所以它是可以被優化的。基本上，優化以後就不會有時間與空間效率的問題。
注意: Python 沒有tail recursion 優化，而且stack 深度不到1000。C 要開編譯器開啟最佳化才會做tail recursion 優化。
未完待續
閱讀更多 kGavin 的文章
