基礎程式設計（Java）· CH18
基底條件 · 遞迴步驟 · 展開與回溯 · 階乘 · 費氏 · 河內塔 · 遞迴 vs 迭代 · 導覽地圖
完整內容看 PDF 講義，動手追蹤與試跑看 index。
什麼是遞迴
遞迴＝方法在自己的方法體裡呼叫自己；每次都讓問題更接近最簡單的情況。
兩個必要部位
long factorial(int n) {
if (n <= 1) return 1; // ① 基底條件：終止點
else return n * factorial(n - 1); // ② 遞迴步驟：縮小後呼叫自己
}基底條件＝可直接回答、不再呼叫自己；遞迴步驟＝引數縮小一級、收斂到基底。
展開與回溯
factorial(4) = 4*6 = 24。同一方法的多個活動記錄同時疊在堆疊上，各有自己的 n。
呼叫堆疊
展開深度＝同時疊的框數。漏基底／不收斂 → 疊到爆 → StackOverflowError。
費氏數列
long fib(int n) {
if (n == 0 || n == 1) return n; // 兩個基底條件
else return fib(n - 1) + fib(n - 2); // 呼叫自己兩次
}
// 0 1 1 2 3 5 8 13 21 34分叉呼叫樹，子問題被重算 → 呼叫次數指數成長，大 n 很慢。
河內塔
void hanoi(int n, char from, char to, char aux) {
if (n == 1) { print(from + " -> " + to); } // 基底
else {
hanoi(n-1, from, aux, to); // ① n-1 片 → 輔助柱
print(from + " -> " + to); // ② 最大片 → 目標
hanoi(n-1, aux, to, from); // ③ n-1 片 → 目標
}
}n 片需 2ⁿ − 1 次搬移；hanoi(3) 共 7 步。
遞迴 vs 迭代
天然遞迴問題（樹、河內塔）用遞迴；線性累加用迭代更省。
陷阱
long bad(int n) {
return n * bad(n - 1); // 缺基底條件！停不下來
} // → StackOverflowError三個必檢點：有沒有基底條件、引數有沒有朝基底收斂、所有路徑都會抵達基底嗎。
接下來