遞迴

一個函式可以叫自己。 · ⏱ 約 30 分鐘

你會學到三件事

1. 一個函式可以叫自己，而那不是作弊
2. 遞迴只有兩個元件：呼叫自己、終止條件
3. 終止條件可以不只一個

開始之前

上一課你做了函式：square(5) 會跑一次 square。 那麼——函式裡面可以呼叫函式嗎？ 可以，你已經做過了（main 裡叫 square）。

那再問一句：它可以叫的那個函式，會不會就是它自己？

一、階乘

5! 的意思是 5 × 4 × 3 × 2 × 1，答案是 120。

它有一個特性：

5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
...

也就是說，「算 5 的階乘」這件事，可以用「算 4 的階乘」來完成。 而算 4 的階乘，又可以用算 3 的階乘來完成。

寫成程式：

int f(int n) {
    if (n <= 1) return 1;     // ② 終止條件
    return n * f(n - 1);      // ① 呼叫自己
}

跑 f(5) 的時候實際發生的事：

f(5) = 5 × f(4)
       f(4) = 4 × f(3)
              f(3) = 3 × f(2)
                     f(2) = 2 × f(1)
                            f(1) = 1      ← 到底了，開始往回算
                     f(2) = 2 × 1  = 2
              f(3) = 3 × 2  = 6
       f(4) = 4 × 6  = 24
f(5) = 5 × 24 = 120

⚠️ 往下叫到底，才開始往回算。 中間那些 f(4)、f(3) 都還沒有答案， 它們在等下面那一層。

二、遞迴只有兩個元件

① 呼叫自己     ——而且每一次都要更靠近終止條件（這裡是 n - 1）
② 終止條件     ——什麼時候不再叫自己（這裡是 n <= 1）

兩個都要有。 少哪一個都會出事：

⚠️ 這和第 10 課迴圈的「三樣東西」是同一件事換個樣子。

每寫完一個遞迴，問兩句：終止條件在哪？每次真的有變小嗎？

完成的樣子

1#include <iostream>2using namespace std;3int f(int n) {4    if (n <= 1) return 1;5    return n * f(n - 1);6}7 8int main() {9    cout << f(5) << endl;10    return 0;11}

到編輯器照著做一次：跟著做

換你了

終止條件可以不只一個

費氏數列是這樣長的：0, 1, 1, 2, 3, 5, 8, 13, ... ——每一項是前兩項相加。

fib(n) = fib(n-1) + fib(n-2)

🔴 它每次要往下叫兩次，所以它需要兩個終止條件： fib(0) = 0 和 fib(1) = 1。

想一下為什麼只寫 fib(0) = 0 不夠——fib(1) 會變成什麼？

寫出來，印出 fib(10)。

到編輯器做這一題：練習：費氏數列

同一件事，兩種寫法

寫兩個函式算最大公因數：一個用迴圈，一個用遞迴。讀進兩個數，兩個答案都印出來。

輾轉相除法只有一句話：gcd(a, b) = gcd(b, a % b)，而 b 變成 0 的時候答案就是 a。 ⚠️ 裁判用的是 48 和 18。

🔴 兩個版本長得很不一樣，而它們做的是同一件事。哪一個比較好讀？跟旁邊的人不一定同答案。

到編輯器做這一題：練習：最大公因數，兩種寫法

做一個

河內塔：有三根柱子 A、B、C，A 上面疊著 n 個由大到小的盤子。 要把它們全部搬到 C，規則兩條：一次只能搬一個、大的不能壓在小的上面。

用迴圈很難想。用遞迴只有三句話：

① 先把上面 n-1 個搬到 B（借 C 當中繼）
② 把最大的那個從 A 搬到 C
③ 再把 B 上的 n-1 個搬到 C（借 A 當中繼）

而①和③就是同一個問題，只是小了一號——那正是遞迴。

把每一步印出來，一行一步，格式是 A -> C。 ⚠️ 裁判用的是 3 個盤子（應該會有 7 行）。

🔴 先自己數一數：n 個盤子要搬幾次？1 個是 1 次、2 個是 3 次、3 個是 7 次…… 跟旁邊的人猜一下 n = 20 要幾次，再用程式跑跑看。

到編輯器做這一題：做一個：河內塔，把每一步印出來

這一課你做了什麼

• 你寫了一個叫自己的函式，而且找得出它的終止條件
• 你寫了一個有兩個終止條件的遞迴
• 你把同一件事用迴圈和遞迴各寫了一遍

如果卡住了