Recursion

歡迎來到遞迴（Recursion）的世界！

在本章中，我們將探討編程中最優雅且強大的概念之一：遞迴（Recursion）。起初你可能會覺得這有點「燒腦」，但別擔心！我們會一步步拆解。當你讀完這些筆記後，你會發現遞迴其實就是一種看待問題的新角度——透過將大問題拆解成較小且相同的子問題來解決。

想像一下俄羅斯套娃（Matryoshka）。為了拿到最中間的小娃娃，你必須先打開一個大娃娃，接著是稍微小一點的，再小一點的，直到最後找到那個不能再打開的最小娃娃為止。

1. 什麼是遞迴？

在計算機科學中，當一個函式（function）在自己的程式碼中呼叫自己時，就會發生遞迴。這是一種解決問題的方法，其解決方案取決於相同問題在較小規模時的解法。

1.1 遞迴的基本特徵（課程大綱 1.4.1）

每個成功的遞迴函式都必須具備這三個基本特徵。若缺少它們，你的程式可能會當機或無限執行下去！

1. 基準情況（Base Case）： 這是「停止條件」。它是問題最簡單的版本，可以直接得到答案，無需進一步遞迴。它能防止函式無限地自我呼叫。
2. 遞迴步驟（Recursive Step）： 這是函式自我呼叫的部分。它處理的是原始問題的一個稍微縮小的版本。
3. 邁向基準情況（Progress Toward the Base Case）： 每次函式呼叫自己時，它必須更接近基準情況（通常透過改變變數值來達成）。如果你沒有向基準情況推進，就會產生無限遞迴（Infinite Recursion）。

快速複習盒：
記住 B.R.P. 口訣：
- Base Case (基準情況 - 停止)
- Recursive Step (遞迴步驟 - 重複)
- Progress (進度 - 逐步靠近終點)

2. 閱讀與編寫遞迴演算法（課程大綱 1.4.2）

讓我們看看經典範例：計算數字的階乘（Factorial）。
\(n\) 的階乘（記作 \(n!\)）是所有小於或等於 \(n\) 的正整數的乘積。
範例：\(4! = 4 \times 3 \times 2 \times 1 = 24\)

階乘的遞迴定義：

- 若 \(n = 0\)，答案為 \(1\)（基準情況）
- 若 \(n > 0\)，答案為 \(n \times (n-1)!\)（遞迴步驟）

Python 實作：

def factorial(n):
    if n == 0: # 基準情況
        return 1
    else: # 遞迴步驟
        return n * factorial(n - 1) # 進度：(n - 1) 讓我們更接近 0

你知道嗎？ 如果你忘記寫基準情況，電腦會不斷地在記憶體中增加「層數」，直到耗盡記憶體空間。這就是所謂的堆疊溢位（Stack Overflow）！

3. 追蹤遞迴：遞迴樹（課程大綱 1.5.5）

當遞迴函式被呼叫時，電腦不會立即完成第一次呼叫。它會「暫停」目前的呼叫並開始一個新的。我們可以使用遞迴樹（Recursion Tree）來視覺化這個過程。

讓我們追蹤 factorial(3)：

1. 呼叫 factorial(3)。它需要 \(3 \times factorial(2)\)。（暫停！）
2. 呼叫 factorial(2)。它需要 \(2 \times factorial(1)\)。（暫停！）
3. 呼叫 factorial(1)。它需要 \(1 \times factorial(0)\)。（暫停！）
4. 到達基準情況： factorial(0) 回傳 \(1\)。
5. 現在我們開始「解開」（Unwind）：
    - factorial(1) 變成 \(1 \times 1 = 1\)
    - factorial(2) 變成 \(2 \times 1 = 2\)
    - factorial(3) 變成 \(3 \times 2 = 6\)
最終答案：6

重點總結： 追蹤過程能幫你理解「解開」的過程（將值一層層傳回）是如何產生最終結果的。

4. 比較遞迴與迭代（課程大綱 1.4.3）

大多數可以用遞迴解決的問題，也可以用迭代（Iteration）（例如 for 或 while 迴圈）來解決。它們的比較如下：

4.1 遞迴

優點：
- 程式碼通常更短、更簡潔、更優雅。
- 對於本質上是遞迴的問題（如樹的遍歷或「河內塔」問題）更容易求解。

缺點：
- 記憶體使用：較高。每次呼叫都會佔用呼叫堆疊（Call Stack）的空間。
- 速度：通常較慢，因為多個函式呼叫會產生額外的負擔（overhead）。

4.2 迭代

優點：
- 記憶體使用：較低。它重複使用相同的空間。
- 速度：通常較快，因為沒有函式呼叫的額外負擔。

缺點：
- 對於某些數學問題，程式碼可能會變得非常複雜且凌亂。

類比：
- 迭代就像是在跑道上跑圈。你處在同一個位置，只是重複同樣的動作。
- 遞迴就像是走旋轉樓梯。你雖然在做同樣的圓周運動，但每次都處在不同的高度（層級）。

5. 常見的錯誤避坑指南

1. 遺失基準情況：這是最常見的錯誤！一定要問自己：「這什麼時候會停止？」
2. 沒有進度：如果你在 factorial(n) 內部呼叫 factorial(n)，\(n\) 的值永遠不會變，你就永遠無法到達基準情況。
3. 遞迴步驟邏輯錯誤：確保拆解問題的方式能導向正確的數學結果。

總結檢核清單

- [ ] 我知道三個基本特徵（基準情況、遞迴步驟、進度）嗎？
- [ ] 我能在一段程式碼中識別出基準情況嗎？
- [ ] 我能解釋為什麼遞迴比迴圈使用更多記憶體嗎？
- [ ] 我能畫出一棵簡單的樹來追蹤遞迴函式嗎？

如果一開始覺得很難，別擔心！ 遞迴需要思維模式的轉換。試著用筆和紙追蹤一些小的範例；這是見證「魔法」發生的最好方法！