Learning Objectives
- 說明遞迴函式的兩個部分：終止條件與遞迴步驟
- 追蹤遞迴呼叫時呼叫堆疊一層層長出、再一層層收回的過程
- 寫出階乘、陣列加總、次方等遞迴函式，並和迴圈寫法比較
- 說明直接照定義寫的費氏數列為什麼會重複計算
- 說明少了終止條件時會發生堆疊溢位
函式呼叫自己
有些問題可以拆成「一個比較小的同類問題，再加上一點點工作」。例如階乘：
- 4! = 4 × 3!
- 3! = 3 × 2!
- 2! = 2 × 1!
- 1! = 1（不用再拆，直接知道答案）
把這個想法寫成程式，就是一個呼叫自己的函式，叫做遞迴（recursion）：
int factorial(int n) {
if (n <= 1) { // 終止條件（base case）
return 1;
}
return n * factorial(n - 1); // 遞迴步驟（recursive case）
}
每個遞迴函式都要有兩個部分：
- 終止條件：問題小到可以直接回答，不再呼叫自己
- 遞迴步驟：把問題變小一點，呼叫自己處理小問題，再用小問題的答案組出原本的答案
每次呼叫都會在呼叫堆疊（call stack）上建立一個新的框架，放這一次呼叫自己的參數和區域變數。
所以 factorial(4) 和 factorial(3) 各有各的 n，彼此不會互相干擾。本課的動畫會讓你看到框架一層層疊上去，又一層層收回來。
階乘：堆疊長出來，再收回去
看右邊的框架：每呼叫一次 factorial 就在下方多一層，最下面那層是目前正在執行的。到 n 是 1 時碰到終止條件，接著每一層依序回傳，把下一層給的答案乘上自己的 n。
呼叫之前與呼叫之後
遞迴函式裡，寫在「呼叫自己」之前的程式，會在往下走的時候執行；寫在之後的程式，要等下面所有層都結束、回到這一層時才執行。 所以同樣是印出 n，放在遞迴呼叫前面或後面，印出來的順序剛好相反。
往下走、再往回走
countdown(3) 往下呼叫到 countdown(0)。注意第 10 行的「下去」在往下的途中印出，第 12 行的「回來」要等到下一層結束才印出，順序是 1、2、3。
想一想：追蹤遞迴
下面的程式會印出什麼？
int mystery(int n) {
if (n == 0) return 0;
return n % 10 + mystery(n / 10);
}
int main() {
cout << mystery(345);
}
下面的程式會印出什麼？
void show(int n) {
if (n == 0) return;
show(n - 1);
cout << n;
}
int main() {
show(3);
}
int power(int b, int e) { return b * power(b, e - 1); } 這個函式少了什麼？
遞迴與迴圈
能用遞迴寫的，也都能用迴圈寫，兩者各有長處：
| 遞迴 | 迴圈 | |
|---|---|---|
| 程式長相 | 和數學定義、問題結構很接近，常常比較短 | 要自己安排變數記錄進度 |
| 執行成本 | 每次呼叫都要建立框架，比較慢、佔堆疊空間 | 通常比較快、省空間 |
| 適合 | 問題本身是遞迴結構：樹狀資料、資料夾、分治法（二分搜尋、合併排序）、窮舉所有組合 | 單純的重複、一路往前算 |
費氏數列的定義是 F(0) = 0、F(1) = 1、F(n) = F(n − 1) + F(n − 2)。照定義直接寫成遞迴非常直覺，
但 fib(n) 會呼叫 fib(n − 1) 和 fib(n − 2)，fib(n − 1) 又會再算一次 fib(n − 2)……同樣的值被算了很多次，
呼叫次數大約每多 1 就乘上 1.6 倍，fib(40) 要呼叫超過 3 億次。用迴圈從小往大算，每個值只算一次。
費氏數列：重複計算
calls 是全域變數，記錄 fib 一共被呼叫幾次。播放時注意同一個參數（例如 n 是 2）的框架出現了好幾次。最後和迴圈版本比較：fibLoop 只跑 5 圈。這一段步數比較多，可以拖拉進度條快轉。
遞迴的應用：二分搜尋
在排好序的陣列裡找一個數，不必從頭一個一個看：先看中間那一個，目標比較小就只找左半邊，比較大就只找右半邊。 每次都把範圍砍掉一半，8 個元素最多看 4 次，100 萬個元素也只要看 20 次左右。
「在左半邊找」和「在右半邊找」都是同一個問題、只是範圍變小，所以很適合寫成遞迴：參數 low、high 代表目前的搜尋範圍，
範圍變成空的（low > high）就是找不到的終止條件。
遞迴二分搜尋
每一層框架的 low、high 代表這一層負責的範圍，範圍每次少一半。找到之後，答案一層層原封不動往上傳回 main。第二次找 10，範圍縮到空的，回傳 -1。
沒有終止條件：堆疊溢位
每一層遞迴呼叫都在呼叫堆疊上佔一塊空間，要等到函式回傳才會釋放。如果終止條件寫錯或忘了寫，呼叫會一直疊下去，
直到用光堆疊空間（Linux 上預設通常是 8 MB），程式當掉，這叫做堆疊溢位（stack overflow）。在 Linux 上通常會看到 Segmentation fault。
一個框架通常只有幾十個位元組，真正的程式要疊到幾十萬層才會溢位。為了讓你在幾步之內就看到結果，下面的範例在每一層放了一個約 1.2 MB 的陣列。 同樣的道理，遞迴層數很深時（例如對 10 萬個元素做逐一遞迴），即使終止條件正確也可能溢位，這時就改用迴圈。
堆疊溢位
dig 每一層都呼叫下一層，沒有任何條件會讓它停下來。右邊的框架一直變多，到第 8 層時堆疊空間不夠了。第 14 行永遠不會執行。
想一想：效率與應用
下面的程式會印出什麼？
int calls = 0;
int fib(int n) {
calls++;
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
fib(4);
cout << calls;
}
下面的程式會印出什麼？
int power(int b, int e) {
if (e == 0) return 1;
return b * power(b, e - 1);
}
int main() {
cout << power(3, 4);
}
關於遞迴與迴圈，下列哪一個說法正確？
動手寫：遞迴加總與次方
用遞迴完成兩個函式，不要用迴圈：
sumArray(arr, n)：回傳陣列前 n 個元素的和。終止條件是 n 為 0；遞迴步驟是「前 n - 1 個的和」加上第 n 個元素arr[n - 1]power(b, e)：回傳 b 的 e 次方，e 是 0 時回傳 1
重點回顧
- 遞迴函式呼叫自己，一定要有終止條件（直接回答）和遞迴步驟（把問題變小，呼叫自己）
- 每次呼叫都在呼叫堆疊上建立新的框架，各有自己的參數與區域變數；碰到終止條件後，各層依序回傳
- 寫在遞迴呼叫之前的程式在往下時執行，寫在之後的程式在往回時執行，順序相反
- 照定義寫的費氏數列會重複計算同樣的值，呼叫次數快速增加；改用迴圈從小往大算，每個值只算一次
- 二分搜尋每次把範圍砍半，範圍變空就是找不到的終止條件
- 少了終止條件，或層數太深，會用光堆疊空間，發生堆疊溢位