Learning Objectives
- 說出遞迴函式的兩個部分：終止條件與遞迴關係
- 追蹤呼叫堆疊：每一次呼叫疊上一個新的框架，回傳時再一層一層拿掉
- 用遞迴寫出階乘、串列加總與二分搜尋
- 畫出費氏數列的遞迴樹，說明重複計算讓呼叫次數暴增
- 用遞迴解河內塔，說明 n 個圓盤要移動 2ⁿ - 1 次
把大問題交給「小一號的自己」
資料夾裡有資料夾，裡面又有資料夾；要算出整個資料夾佔多少空間，最自然的說法是：「把裡面每個檔案的大小加起來，再加上每個子資料夾的大小」。 「子資料夾的大小」和原本的問題一模一樣，只是規模小一點。這種用自己來定義自己的寫法，就是遞迴（recursion）。
一個遞迴函式一定有兩個部分：
| 部分 | 作用 | 階乘的例子 |
|---|---|---|
| 終止條件（base case） | 問題小到可以直接回答，不再呼叫自己 | 0! = 1 |
| 遞迴關係（recursive case） | 把問題縮小一號，交給自己處理，再用結果算出答案 | n! = n × (n-1)! |
寫遞迴的時候，你只要相信「小一號的問題，函式自己會算對」，專心想兩件事：最小的情況怎麼回答，以及怎麼用小一號的答案組出現在的答案。
階乘：呼叫一層一層疊上去，再一層一層回來
上方的遞迴樹依呼叫順序長出節點；factorial(4) 呼叫 factorial(3)，factorial(3) 又呼叫 factorial(2)……一路到 factorial(0) 才停。注意輸出的順序：「呼叫」由大到小印出，「回傳」卻是由小到大，因為每一層都要等下一層算完，才能算出自己的結果。動畫下方的變數區可以看到同時有好幾個 factorial 框架疊在一起。
呼叫堆疊：每一層都有自己的變數
每呼叫一次函式，電腦就在呼叫堆疊（call stack）上放一個新的框架（frame），裡面存著這一次呼叫自己的參數和區域變數。
所以 factorial(4) 的 n 是 4、factorial(3) 的 n 是 3，彼此不會蓋掉。函式回傳時，它的框架被拿掉，控制權回到下面那一層，從剛才停下來的地方繼續。
呼叫 factorial(4) 堆疊（上面是正在執行的）
呼叫 factorial(3) factorial(0) n = 0 ← 最後放上去，最先回傳
呼叫 factorial(2) factorial(1) n = 1
呼叫 factorial(1) factorial(2) n = 2
呼叫 factorial(0) factorial(3) n = 3
factorial(4) n = 4 ← 最先放上去，最後回傳
最後放上去的最先拿掉，這就是第 10 課會正式介紹的堆疊（stack）：後進先出。遞迴有多深，堆疊就有幾層，所以遞迴也要用記憶體，空間複雜度至少是 O(遞迴深度)。
忘了終止條件會怎樣？ 下面這個函式沒有「n 是 0 就停」的判斷，會一直呼叫下去：
def factorial(n):
return n * factorial(n - 1) # 沒有終止條件
堆疊的空間有限，框架越疊越多，最後就會出錯：Python 預設大約疊到 1000 層就丟出 RecursionError，Java 丟出 StackOverflowError，C++ 通常是程式直接當掉（堆疊溢位）。
終止條件寫了卻永遠碰不到（例如 n 從負數開始、每次減 1，永遠不會等於 0），結果也一樣。寫遞迴時要確認：每次呼叫都讓問題變小，而且一定會小到終止條件。
串列加總：自己這一個，加上後面全部
total(a, i) 的意思是「從索引 i 到最後的總和」。它把問題拆成「a[i]」加上「total(a, i + 1)」；i 走到陣列長度時，後面已經沒有元素，總和是 0。看遞迴樹的回傳值怎麼從 0 一路加回 18。
想一想：終止條件與呼叫順序
下面的程式會印出什麼？
def f(n):
if n == 0:
return
print(n, end=" ")
f(n - 1)
print(n, end=" ")
f(3)
執行 factorial(4) 時，正在執行 factorial(0) 的那一刻，呼叫堆疊上同時有幾個 factorial 的框架？
def g(n): return g(n - 2) if n != 0 else 0，呼叫 g(5) 會怎樣？
費氏數列：一次呼叫自己兩次
費氏數列（Fibonacci）是 0、1、1、2、3、5、8、13……從第三項開始，每一項是前兩項的和：
- 終止條件：fib(0) = 0、fib(1) = 1
- 遞迴關係：fib(n) = fib(n - 1) + fib(n - 2)
照定義直接寫成遞迴，非常好讀。但這次每一層會呼叫自己兩次，遞迴樹會往兩邊分岔。下面的範例用一個全域變數 calls 數一數 fib 一共被呼叫幾次。
費氏數列的遞迴樹：同樣的東西算了好幾次
只是算 fib(5)，fib 就被呼叫了 15 次。看遞迴樹：fib(3) 出現 2 次、fib(2) 出現 3 次、fib(1) 出現 5 次，每一次都從頭重算。走到最後，比較遞迴樹的左半邊（fib(4)）和右半邊（fib(3)），右半邊整棵都在左半邊裡算過了。
呼叫次數長得比 n 快很多
把 n 改大，呼叫次數會怎麼變？下表是實際數出來的：
| n | fib(n) | fib 被呼叫的次數 |
|---|---|---|
| 5 | 5 | 15 |
| 10 | 55 | 177 |
| 20 | 6,765 | 21,891 |
| 30 | 832,040 | 2,692,537 |
| 40 | 102,334,155 | 331,160,281 |
n 每多 10，呼叫次數大約變成 120 倍，成長的速度是指數級的（大約是 1.6ⁿ）。問題出在重複計算：fib(38) 在算 fib(40) 時被重算了 2 次、fib(30) 被重算了 89 次。
解法是把算過的答案記下來，下次直接拿來用，這叫記憶化（memoization），每個 fib(k) 只要算一次，呼叫次數就從指數級降到大約 2n。第 21 課「動態規劃入門」會從這裡接著講。
這不代表遞迴不好；遞迴樹裡如果沒有重複的子問題（例如下面的二分搜尋、河內塔，以及第 07 課的合併排序），遞迴就是又清楚又有效率的寫法。
二分搜尋的遞迴寫法
第 04 課的二分搜尋用迴圈更新 lo、hi。換個角度看：「在 [lo, hi] 裡找目標」，比過中間之後，就變成「在左半邊找」或「在右半邊找」，是同一個問題的小一號版本。
- 終止條件 1：
lo > hi，範圍空了，回傳 -1 - 終止條件 2：
a[mid]剛好等於目標，回傳 mid - 遞迴關係：目標比較大就在
[mid + 1, hi]裡找，比較小就在[lo, mid - 1]裡找
每一層只呼叫自己一次，所以遞迴樹是一條直線，不會分岔；深度最多約 log₂n 層。
遞迴版二分搜尋：每一層只看一半
和第 04 課的迴圈版比較：迴圈版是同一個框架裡改 lo、hi，遞迴版是每一層都有自己的 lo、hi。找到之後，答案要經過每一層的 return 一路傳回最外層。遞迴樹是一條直線，因為每一層只呼叫一次自己。
河內塔：只想最大的那一個
河內塔（Tower of Hanoi）是 1883 年法國數學家 Lucas（Édouard Lucas）發表的益智遊戲。三根柱子 A、B、C，A 上由大到小疊著 n 個圓盤，要全部搬到 C，規則是：
- 一次只能搬一個圓盤，而且只能搬最上面那一個
- 大的圓盤不能放在小的圓盤上面
直接想「每一步怎麼搬」很難；用遞迴只要想最大的那個圓盤：
- 把上面 n - 1 個圓盤從 A 搬到 B（借用 C）：這是小一號的同一個問題
- 把最大的圓盤從 A 搬到 C
- 把 B 上的 n - 1 個圓盤搬到 C（借用 A）：又是小一號的同一個問題
終止條件是只剩 1 個圓盤：直接搬過去。
河內塔：3 個圓盤搬 7 次
上方每一列是一根柱子，數字是圓盤大小，左邊是底部。遞迴樹的每個節點都分成「左邊的 n - 1」「中間搬一次」「右邊的 n - 1」，所以搬動次數 = 2 × (n - 1 個的次數) + 1：1 個要 1 次、2 個要 3 次、3 個要 7 次。
河內塔要搬幾次
令 T(n) 是搬 n 個圓盤的次數：T(1) = 1，T(n) = 2 × T(n - 1) + 1。一路展開：
| n | 1 | 2 | 3 | 4 | 5 | 10 | 20 |
|---|---|---|---|---|---|---|---|
| T(n) | 1 | 3 | 7 | 15 | 31 | 1,023 | 1,048,575 |
規律是 T(n) = 2ⁿ - 1。這不是程式寫得不好：可以證明 2ⁿ - 1 已經是最少的次數，因為最大的圓盤至少要搬一次，而搬它之前、之後，上面 n - 1 個都得整疊搬一次。 傳說中 64 個圓盤要搬 2⁶⁴ - 1 次，大約是 1.8 × 10¹⁹；一秒搬一次也要搬五千多億年。
這個公式和費氏數列的呼叫次數一樣是指數成長，但原因不同：河內塔是答案本身就需要這麼多步，費氏數列是同樣的子問題被重算，後者可以用記憶化省掉。
想一想：遞迴樹有多大
把範例的 fib(5) 改成 fib(6)，最後印出的呼叫次數是多少？
河內塔有 10 個圓盤，最少要搬幾次？
在 1,000,000 個已排序的元素裡用遞迴版二分搜尋，最多會疊到大約幾層？
實作：各位數字的和
請用遞迴完成 digit_sum(n)（C++／Java 叫 digitSum）：回傳非負整數 n 每一位數字的和，例如 2026 → 2 + 0 + 2 + 6 = 10。想一想：n 只有一位數時答案是什麼？n % 10 是最後一位，n / 10（整數除法）是去掉最後一位的數。
重點整理
- 遞迴函式有兩個部分：終止條件直接回答最小的情況，遞迴關係把問題縮小一號交給自己
- 每次呼叫都在呼叫堆疊上放一個新框架，各有自己的變數；最後呼叫的最先回傳。遞迴多深，堆疊就多深
- 沒有終止條件，或終止條件碰不到，會一直疊到堆疊溢位（Python
RecursionError、JavaStackOverflowError） - 費氏數列的直接遞迴會重複計算同樣的子問題，呼叫次數指數成長；第 21 課用記憶化解決
- 遞迴版二分搜尋每層只呼叫一次，深度約 log₂n；河內塔 n 個圓盤要搬 2ⁿ - 1 次，這是答案本身的大小
下一課：選擇、插入、氣泡三種簡單的排序。之後第 07 課的合併排序會再用到遞迴：把陣列切成兩半，各自排好，再合併起來。