函式與遞迴

給一段程式取個名字，之後就叫得動它。 · ⏱ 約 35 分鐘

你會學到三件事

1. 怎麼自己做一個函式（而 main 一直都是一個）
2. 參數和回傳值：東西怎麼進去、答案怎麼出來
3. 遞迴：一個函式叫自己

開始之前

第 2 課你給一個值取了名字（變數）。 這一課你要給一段程式取名字。

而其實你第 1 課就見過了——main 就是一個函式， v.push_back() 也是（只是那個是別人寫好的）。

一、做一個

int square(int n) {
    return n * n;
}

四個部位：

int    square    (int n)     { return n * n; }
 ↑        ↑         ↑                ↑
回傳     名字      參數            身體
什麼               ——進去的東西

用它：

cout << square(5) << endl;    // 25

square(5) 的意思是「跑一次 square，把 5 當成 n」， 而整個 square(5) 就變成 25 這個值。

⚠️ 函式要寫在 main 外面。 寫在 main 裡面是另一回事（第 Python 銜接第 6 課課會提）。

二、return 有兩個作用

return n * n;

它同時做兩件事：

1. 把 n * n 算出來的值交出去
2. 立刻結束這個函式——後面的行不會跑

所以 return 之後寫東西是沒有意義的。 （第 1 課那個「印不出來」的坑就是這個。）

不需要交出東西的函式，回傳型態寫 void：

void say() {
    cout << "hi" << endl;
}

三、遞迴：函式叫自己

階乘：5! = 5 × 4 × 3 × 2 × 1。

它有一個特性：5! 就是 5 × 4!。也就是說， 「算 5 的階乘」這件事，可以用「算 4 的階乘」來完成。

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      ← 出口，開始往回算

答案是 120。

四、遞迴一定要有兩樣東西

① 出口       ——什麼時候不再叫自己（這裡是 n <= 1）
② 縮小       ——每一次都要更靠近出口（這裡是 n - 1）

⚠️ 這和第 10 課迴圈的「三樣東西」是同一件事換個樣子： 少了出口就是無窮迴圈，只是這次會把記憶體用光（叫做 stack overflow）。

每寫完一個遞迴，問兩句：出口在哪？每次真的有變小嗎？

完成的樣子

int f(int n) {
    if (n <= 1) return 1;
    return n * f(n - 1);
}

int main() {
    cout << f(5) << endl;
    return 0;
}

換你了

用迴圈（不用遞迴）寫出同一個階乘，確認答案一樣是 120。

想一下：哪一種比較好讀？哪一種比較省記憶體？ （沒有標準答案——階乘用迴圈比較好，而下一階段的樹和圖用遞迴會好非常多。）

這一課你做了什麼

• 你自己做了一個函式，有參數也有回傳值
• 你知道 return 同時「交出值」和「結束函式」
• 你寫了一個叫自己的函式，而且找得出它的出口

如果卡住了