D. 遞迴

上冊 7.1 教過：一個函式可以呼叫另一個函式。遞迴（recursion）就是函式呼叫它自己——聽起來像繞口令，真正做這件事的只有一行：

#include <iostream>
using namespace std;

int fact(int n) {
    if (n == 1) return 1;          // 終止條件：不再呼叫自己
    return n * fact(n - 1);        // 呼叫自己，而且問題變小了
}

int main() {
    cout << fact(4) << '\n';
    return 0;
}

執行結果：

fact(n) 算的是 $1$ 乘到 $n$ 的連乘積： $n$ 乘上「 $1$ 乘到 $n-1$ 的連乘積」，而後面那一段又丟回同一個函式去算。遞迴用到的零件只有函式、if 與 return，所以這種程式碼搬到 C 題本上幾乎原封不動，差別只在輸入輸出那幾行（A 節）。

¶跟著呼叫走一遍

讀遞迴的唯一方法是照著跑一次。上面那支程式從 fact(4) 開始：

呼叫	這一層在做什麼	回傳
`fact(4)`	要 `4 * fact(3)`，先往下	$24$
`fact(3)`	要 `3 * fact(2)`，先往下	$6$
`fact(2)`	要 `2 * fact(1)`，先往下	$2$
`fact(1)`	命中終止條件，不再往下	$1$

這張表要讀兩趟：由上往下是呼叫一層層展開，由下往上是答案一層層回傳（ $1 \to 2 \to 6 \to 24$ ）。中間那幾層在下面算完之前全部卡在原地等——這是遞迴最反直覺的地方。

¶兩個必備零件

任何一支停得下來的遞迴都有這兩樣：

終止條件：某個情況直接給答案，不再呼叫自己（fact 是 n == 1）。
每次呼叫都更靠近終止條件：fact(n - 1) 的參數一路變小，遲早踩到 $1$ 。

少了第一樣，函式就一直呼叫下去，程式停不下來。所以讀到遞迴，第一件事是找出終止條件在哪、參數往哪個方向走；把 n - 1 寫成 n，或條件寫 n == 1 卻從 $0$ 開始，都會讓它永遠停不了。

另一個一定會遇到的例子是輾轉相除法求最大公因數：

int gcd(int a, int b) {
    if (b == 0) return a;          // 終止條件
    return gcd(b, a % b);
}

gcd(24, 18) 的路線是 gcd(24, 18) → gcd(18, 6) → gcd(6, 0)，回傳 $6$ 。餘數每輪都變小，一定停得下來。

¶印在呼叫之前，還是之後？

同一個遞迴，把 cout 擺在呼叫自己的前面或後面，輸出順序會完全相反。讀遞迴時要特別留意那一行的位置：

#include <iostream>
using namespace std;

void pre(int n) {
    if (n == 0) return;
    cout << ' ' << n;              // 印在呼叫「之前」
    pre(n - 1);
}

void post(int n) {
    if (n == 0) return;
    post(n - 1);
    cout << ' ' << n;              // 印在呼叫「之後」
}

int main() {
    cout << "pre:";
    pre(3);
    cout << '\n';
    cout << "post:";
    post(3);
    cout << '\n';
    return 0;
}

執行結果：

pre: 3 2 1
post: 1 2 3

pre 先印再往下，數字是在展開的路上印出來的， $3$ 數到 $1$ ；post 先往下、回來才印，數字是在回傳的路上印出來的， $1$ 數到 $3$ 。兩支程式的差別只有那一行的位置。

¶費氏數列：同一個東西算很多遍

#include <iostream>
using namespace std;

int calls = 0;                     // 記錄 fib 一共被呼叫幾次

int fib(int n) {
    calls++;
    if (n <= 2) return 1;          // 終止條件：前兩項都是 1
    return fib(n - 1) + fib(n - 2);
}

int main() {
    int ans = fib(10);
    cout << ans << ' ' << calls << '\n';
    calls = 0;
    ans = fib(30);
    cout << ans << ' ' << calls << '\n';
    return 0;
}

執行結果：

55 109
832040 1664079

fib(10) 的答案是 $55$ ，卻呼叫了 $109$ 次；fib(30) 要呼叫一百六十六萬次。原因是 fib(n - 1) 與 fib(n - 2) 兩邊會各自把同一批小問題重算一遍。識讀題問「fib(6) 一共被呼叫幾次」時，照著展開數就對了；怎麼讓它不要重算，是後面課程的事。

¶互遞迴

兩個函式互相呼叫對方，一樣是遞迴——例如用「偶數的前一個是奇數」互相定義。這裡會冒出一個新寫法：兩個函式互相用到對方，不可能兩個都寫在對方前面。解法是先補一行只有標頭、結尾是分號的宣告，告訴編譯器這個函式存在、本體寫在後面，上冊 7.1「被呼叫的函式要先定義」就滿足了：

int isOdd(int n);                  // 只宣告，本體寫在下面

int isEven(int n) {
    if (n == 0) return 1;
    return isOdd(n - 1);
}

int isOdd(int n) {
    if (n == 0) return 0;
    return isEven(n - 1);
}

判讀方法完全一樣：找終止條件，然後跟著呼叫走一遍。

正文的合併排序法（11.12）本書用的是只有迴圈的簡化寫法；教科書上的經典寫法正是靠遞迴——「把左半排好、把右半排好，再合併起來」，其中「排好」兩個字就是呼叫自己，終止條件則是「只剩一個元素就不用排了」。讀完這一節，那種寫法你也讀得動了。

← C. 位元運算 E. 佇列與堆疊 →