函式自己呼叫自己,把大問題拆成同樣形狀的小問題。分治、回溯、DP 的共同地基。
base case(終止條件) —— 小到不用再拆的情況,直接給答案(例如 factorial(1) = 1)。這是「煞車」。
遞迴步驟(recursive case) —— 用「更小的自己」來解,並確保每次都往 base case 靠近。
少了 base case —— 停不下來,直接 RecursionError(堆疊爆掉)。
問題沒有變小 —— 一樣停不下來。每次呼叫,參數一定要更接近終止條件。
每次呼叫都「暫停自己、等子呼叫」 —— 這些等待中的呼叫,一層層疊在呼叫堆疊上。
一路拆到 base case(往下疊) —— 這叫「遞」。
從 base case 開始一層層回傳(往上收) —— 這叫「迴」。
所以遞迴跟堆疊是一體兩面 —— 就是「堆疊」那頁講的 call stack。下面的視覺化就是在演這個。
樹狀 / 巢狀 / 分治問題 —— 遞迴通常更短、更貼近問題本身(走訪樹、全排列、河內塔)。
單純線性重複 —— 用迴圈往往更快、更省記憶體(不會一直堆呼叫)。
遞迴的代價 —— 每層呼叫有開銷,還可能堆疊爆掉(Python 遞迴上限約 1000)。
有些遞迴會重複算 —— 費式數列直接遞迴會爆炸,要加記憶化把算過的存起來(範例 4,DP 的地基)。
O(n)、砍半拆是 O(log n)、無腦分兩岔又不記憶是 O(2ⁿ)。打開一個,裡面還有更小的一個,一直到最小那個(base case),再一層層蓋回去。
片中有人在看電影,那部裡又有人在看…看到最裡面那部演完,才一層層回到最外面。
打開一層點進下一層,點到最底沒有子資料夾了,再一層層退回來。
看 factorial(4) 怎麼跑:先一路呼叫更小的自己(遞,堆疊往下疊),碰到 factorial(1) 這個 base case 就回傳,再一層層把答案乘回去(迴,堆疊往上收)。紫色是正在動的那層、綠色是已回傳、琥珀是還在等子呼叫。
從階乘、累加、費式數列(天真 vs 記憶化),到快速冪、反轉、河內塔、攤平巢狀、遞迴二分搜尋。
❌ 忘了 base case —— 停不下來,RecursionError(堆疊爆掉)。
❌ 遞迴沒讓問題變小 —— 每次呼叫的參數要更接近 base case,不然一樣停不下來。
❌ 天真遞迴重複算 —— 費式數列這種要加記憶化,不然 O(2ⁿ)。
❌ 遞迴太深 —— 資料很深(幾萬層)會撞上限;改用迴圈 + 自己的堆疊,或 sys.setrecursionlimit 調高。
factorial(4) 的呼叫堆疊會疊到多深?回傳值由內而外依序是多少?(用視覺化對答案)fib(5),其中 fib(2) 大約被呼叫幾次?為什麼加了記憶化就只算一次?把答案打到對話裡,我幫你對。