遞迴：套娃的數學版｜由淺至深演算法

想像俄羅斯套娃

打開大娃娃 → 裡面有個小娃娃 → 打開小娃娃 → 裡面有更小的娃娃 → …… 直到打開最小那個娃娃——它裡面沒東西，你就停下來。

遞迴 (Recursion) 就是這個動作：函數呼叫自己，直到遇到「最小情況」就停。

遞迴的兩個關鍵零件

寫遞迴只要回答兩個問題：

① 什麼時候停？(Base Case)

最小的、不需要再分解的情況。沒有這個會無限遞迴 → 程式爆炸。

② 怎麼縮小問題？(Recursive Case)

把問題切成更小的版本，丟給自己。注意：要往「停止條件」逼近。

經典例子：階乘

5! = 5 × 4 × 3 × 2 × 1 = 120

換個角度看：5! = 5 × 4!，那 4! 怎麼算？4! = 4 × 3!……

factorial(5)
  = 5 × factorial(4)
        = 4 × factorial(3)
              = 3 × factorial(2)
                    = 2 × factorial(1)
                          = 1  ← Base Case！停！
                    = 2 × 1 = 2
              = 3 × 2 = 6
        = 4 × 6 = 24
  = 5 × 24 = 120  ✓

Pseudocode：

Algorithm factorial(n):

if n ≤ 1: return 1 // Base Case

return n × factorial(n-1) // Recursive Case

經典例子 2：費氏數列

0, 1, 1, 2, 3, 5, 8, 13, 21, … 每個數字是前兩個的和。

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

Algorithm fib(n):

if n ≤ 1: return n

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

⚠️這個寫法有大問題

看起來很漂亮，但慢到嚇人。

算 fib(5) 的遞迴樹：

            fib(5)
          /        \
       fib(4)      fib(3)
       /    \      /    \
    fib(3) fib(2) fib(2) fib(1)
    /   \   ...
 fib(2) fib(1)

fib(3) 被算 2 次、fib(2) 被算 3 次——大量重複計算！複雜度是 O(2ⁿ)——n=50 就跑不完。

解法：動態規劃（下一章），把算過的存起來。

遞迴樹：考試最愛畫的東西

「畫出 fib(4) 的遞迴樹」是經典題目。畫法：

遞迴 vs 迴圈

很多遞迴可以改寫成迴圈，反之亦然。差別：

	遞迴	迴圈
程式碼	通常更短、更接近數學定義	通常較長、更直白
速度	略慢（函數呼叫成本）	較快
記憶體	佔堆疊空間 O(深度)	O(1)
適用	樹、分治、回溯	簡單累加、走訪

寫遞迴的步驟

問：base case 是什麼？ 最小、最簡單的情況。
問：怎麼把 n 的問題變成 n-1（或更小）的問題？
相信遞迴——假設 recurse(n-1) 已經正確了，你只要寫「已知 n-1 的答案，怎麼算 n」。

這叫「遞迴信念」(recursive faith)——學遞迴的最大關卡。

📝考試會這樣考

題型一：給遞迴函數，問 f(某個值) 結果是多少。 畫遞迴樹一步一步算。不要心算，誰心算誰錯。

題型二：畫出 fib(n) 或 factorial(n) 的遞迴樹。 注意每個節點要標清楚 n 值，葉節點是 base case。

題型三：把迴圈改寫成遞迴（或反過來）。 例：把「印 1 到 n」改成遞迴版。

print_to(n):
    if n == 0: return
    print_to(n-1)   // 先印 1 到 n-1
    print(n)        // 再印 n

題型四：分析遞迴複雜度。

factorial(n)：呼叫 n 次 → O(n)。
fib(n)（沒記憶化）：O(2ⁿ)。
MergeSort：T(n) = 2T(n/2) + O(n) → O(n log n)。

這章記住

遞迴 = 自己呼叫自己，需要 base case + 縮小問題。
遞迴樹是分析遞迴的關鍵工具，考試常考。
遞迴漂亮但有重複計算就會爆——下一章看怎麼救它（DP）。