中文（繁體）
中文（简体）
English
DSE ICT｜遞歸與演算法效率 備課指引（導師用）｜二分搜尋為何只需 20 步
學生識寫 for 迴圈，但一見「用遞歸寫」就卡住，或者寫出一個沒有停機條件的函數。這一堂先把呼叫堆疊畫出來，再比較線性與二分搜尋的步驟數，令「效率」變成數得出來的數字。
本堂目標 學生能夠：① 追蹤 factorial(4) 的呼叫堆疊，講出 4 層、答案 24；② 寫出有 base case 的遞歸函數並指出無 base case 會出現 RecursionError；③ 講出在 1,048,576 筆已排序資料上用二分搜尋最多 20 次比較，而線性搜尋最多 1,048,576 次，相差約 52,429 倍；④ 判斷兩層迴圈是 O(n²)、每次把 n 減半是 O(log n)。
01 先備知識（開課前 3 分鐘快檢）
以下任何一項未過關，本堂就會卡住，先補該項：
| 技能 | 快檢題 | 過關標準 |
|---|---|---|
| 函數與參數 | 呼叫函數時，參數放在哪裡？ | 放進該次呼叫自己的 stack frame |
| for 迴圈 | 怎樣把 1 到 n 加起來？ | 累加器由 0 開始，逐個加 |
| 排序 | 二分搜尋之前，資料必須怎樣？ | 必須已排序 |
02 課堂流程（60 分鐘）
| 時間 | 環節 | 導師做什麼 | 學生做什麼 |
|---|---|---|---|
| 0–8 分 | 一條問題開場 | 問：電話簿有一百萬個名，找一個名要揭幾頁？ | 學生多數答「逐頁揭」 |
| 8–20 分 | 追蹤 factorial | 並排寫 factorial(4) → 4×factorial(3) → … → 1 | 畫出 4 層 stack frame，答案 24 |
| 20–32 分 | base case 與深度 | 刪掉 if n == 1 那一行，問會發生甚麼 | 講出 RecursionError、深度等於 n |
| 32–44 分 | 二分搜尋步驟數 | 2^20 = 1,048,576，每切一半就少一個 2 | 得出最多 20 次比較 |
| 44–54 分 | 四類題型 | 追蹤、補 base case、判斷複雜度、算比較次數 | 每類做一題 |
| 54–60 分 | 離場檢查 | 三題口頭或書面 | 兩題以下要重做 |
03 講解腳本（照著說就可以）
第一幕：遞歸不是魔法，是一層層未做完的呼叫
寫 factorial(n)：if n == 1: return 1；else: return n * factorial(n-1)。factorial(4) 未計完就要等 factorial(3)，factorial(3) 又等 factorial(2)，一直落到 factorial(1) 回傳 1，才一層層乘上去：1 → 2 → 6 → 24。畫四個並排的框，箭頭向下是「等待」，向上是「回傳」，學生就會明白「遞歸 = 用堆疊記住未做完的事」。
黑板畫四個 stack frame，箭頭向下是等待、向上是回傳
第二幕：效率是步驟數，不是程式長短
把兩張紙並排：線性搜尋由第一筆掃到最後一筆，最壞 1,048,576 次；二分搜尋每次砍一半，1,048,576 = 2^20，所以最多 20 次。52,429 倍的差距不是「少少快」，是由「等一小時」變成「等一秒」。再補一句：資料未排序就不能二分，排序本身要成本。
兩張紙並排：線性 1,048,576 次 對 二分 20 次
第三幕：同一題目，兩種寫法都要交得出
叫學生用 for 迴圈寫 sum(n)，再用遞歸寫一次，然後比較：迴圈版用一個累加器，記憶體固定；遞歸版每一層佔一個 stack frame，n = 1,000 已經接近 Python 預設的 recursion limit。結論要講清：遞歸是表達方式，不會自動變快；很多時候迴圈更省資源。
板書 for 版與遞歸版並排，標 stack frame 數目
04 必教題型與步驟
| 題型 | 例子 | 步驟 | 答案 |
|---|---|---|---|
| 追蹤 | 寫出 factorial(4) 的呼叫順序與答案 | 由最底層 factorial(1) 開始往回乘 | 4 層、答案 24 |
| 補完 | 給一個缺 base case 的函數，補上停止條件 | 先問「最細的 case 答案係幾」 | if n == 0: return 1 |
| 判斷複雜度 | 兩層 for 迴圈各跑 n 次 | 數最內層執行次數 | O(n²) |
| 計算 | 已排序 1,048,576 筆，二分搜尋最壞比較次數 | 找 2 的次方，或反覆除 2 | 20 次 |
合理性檢查（一定要教）：檢查：log2(1,048,576) = 20，因為 2^20 = 1,048,576，答 21 或 19 都表示除錯時多數或少數了一次。factorial(4) 的 stack 深度是 4，不是 24——24 是答案，不是層數。naive fib(6) 的呼叫次數是 25 次（2×fib(7)−1 = 2×13−1），而 fib(6) 的答案只是 8，這個落差正是「遞歸寫得靚但效率差」的最佳證據。
05 獨立練習三題
| 題目 | 答案 | 想觀察什麼 |
|---|---|---|
| naive fib(6) 總共幾次函數呼叫？ | 25 次 | 2×fib(7)−1，fib(7)=13 |
| 1,000,000 筆資料，線性與二分搜尋最壞各幾次？ | 1,000,000 次與 20 次 | 2^20 剛好超過一百萬 |
| 這段程式錯在哪：def total(n): return n + total(n-1) | 缺 base case | 會 RecursionError，n 永遠不減到停 |
06 學生常見錯誤與糾正句
| 錯誤 | 學生通常這樣寫 | 導師這樣說 |
|---|---|---|
| 漏寫 base case | 「個程式跑到爆，電腦壞咗」 | 「先寫停機那一行，再寫行落去那一行；冇停機條件的遞歸等於死循環。」 |
| 以為遞歸一定較快 | 「遞歸高級啲，所以快啲」 | 「遞歸只係寫法；fib(6) 遞歸要做 25 次呼叫，答案只係 8。」 |
| 在未排序資料上做二分搜尋 | 「我照樣切一半，切到啱為止」 | 「未排序就切，等於亂猜；要麼先 sort，要麼用線性搜尋。」 |
| 把 O(log n) 講成「快一倍」 | 「log n 即係快一半」 | 「n 由 1,024 加到 1,048,576，即 ×1024，步數只由 10 加到 20，加 10 步。」 |
07 家課建議（直接指到練習卷題號）
08 離場檢查（最後 5 分鐘）
| 題目 | 答案 | 判定 |
|---|---|---|
| factorial(5) 等於幾，堆疊有幾層？ | 120，5 層 | 錯：重做第一幕 |
| 已排序 2^20 筆，二分搜尋最多幾次比較？ | 20 次 | 錯一題：下堂前重做代入 |
| naive fib(6) 幾次呼叫？ | 25 次 | 錯兩題以上：回到第二幕 |
09 導師常問
遞歸一定要教嗎？
DSE 課程要求學生讀懂及修正遞歸程式，追蹤與補 base case 是最常見考法。
要背時間複雜度符號嗎？
不用背定義，但要能在 30 秒內把「兩層迴圈」對應到 O(n²)、「每次減半」對應到 O(log n)。
為甚麼二分搜尋答 20 次而不是 10 次？
因為 2^20 才是 1,048,576，10 次只覆蓋 1,024 筆。
本頁為 TutorZone 導師備課指引，內容由 TutorZone 團隊編寫；題目與流程為原創，並非任何學校或出版社的教材。