永遠是兩個部分
遞迴是用自身來定義的函式。每個正確的遞迴函式都恰好有兩個部分。基準情形是一個你能立刻回答、無需再次呼叫的小輸入——它讓過程停下來。遞迴情形做一點點工作，然後在更小的輸入上呼叫同一個函式，相信它會帶回正確答案。
最經典的第一個例子是階乘：n! = n × (n−1)!，而 0! = 1。這個定義本身就是遞迴——基準情形是 0，每一步剝下一個因子，把其餘的推遲下去。
long long fact(int n) {
if (n == 0) return 1; // base case
return n * fact(n - 1); // recursive case: smaller input
}
// fact(4) = 4 * fact(3) = 4 * 3 * fact(2) = ... = 24呼叫堆疊替你記帳
電腦怎麼記得 fact(4) 在 fact(3) 返回後還欠著一個 `4 *`？它用呼叫堆疊——正是你在線性結構那一級見過的後進先出結構。每次呼叫都壓入一個堆疊框，儲存它的區域變數和恢復執行的位置。呼叫返回時，它的堆疊框彈出，控制權交回呼叫者。
Calling fact(3): frames pushed downward, then popped (return).
push fact(3) waits for fact(2)
push fact(2) waits for fact(1)
push fact(1) waits for fact(0)
push fact(0) = 1 <-- base case, returns now
fact(1) = 1*1 = 1 pop
fact(2) = 2*1 = 2 pop
fact(3) = 3*2 = 6 pop --> answer這就是為什麼遞迴像一種信任：你寫 fact(n) 時就當作 fact(n−1) 已經能用了。堆疊默默替你記下沒做完的工作，你自己永遠不必去管。
當遞迴重複勞動：費氏數列
遞迴很優雅，但並不天生高效。費氏數——fib(n) = fib(n−1) + fib(n−2)，其中 fib(0)=0、fib(1)=1——每次會發起兩次遞迴呼叫。畫出遞迴樹就能看到同樣的子問題被一遍遍重算。
fib(5)
____________ fib(5) ____________
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) f1 f1 f0 f1 f0
/ \
f1 f0
fib(3) is computed twice, fib(2) three times ... work explodes.解決辦法是記憶化：第一次算出每個 fib(k) 時就把它記下來，之後直接複用。這能把樹壓成一條線，把 O(2^n) 變成 O(n)。在動態規劃那一級，你會再次遇到這個思想，並大展身手。
遞迴出錯的兩種方式
由於每次呼叫都吃掉一個堆疊框，遞迴有兩種著名的失敗方式。無限遞迴是忘了基準情形（或根本沒朝它靠近），於是函式永遠呼叫自己。堆疊溢位是遞迴太深——即便完全正確的遞迴，如果嵌套上百萬層，也會崩潰，因為堆疊的大小是有限的。
// BUG: no base case is ever reached -> infinite recursion -> stack overflow
int bad(int n) {
return bad(n - 1); // never stops; n races past 0 into negatives
}
// FIX: a base case that the recursion actually reaches
int good(int n) {
if (n <= 0) return 0;
return good(n - 1);
}