遞迴

站在兩面鏡子之間，你會看到影像中的影像中的影像，朝中央縮小。遞迴是一個部分以自身定義的函式：為了解決一個問題，它去解決同一問題的較小版本、並在那個答案上構築。只要每一步都縮小問題、且有一個最小情況能停止這個回退，整件事就會終止。

遞迴函式需要兩個部分：一個基底情況，不再遞迴就直接回傳答案（停止條件）；以及一個遞迴情況，對較小的輸入呼叫自己並結合結果。階乘是教科書範例：factorial(0) 是 1（基底情況），而 factorial(n) 是 n 乘以 factorial(n - 1)（遞迴情況）。每次呼叫都得到自己的堆疊框、握著自己那份 n 的副本，所以呼叫堆疊起來——factorial(3) 等待 factorial(2)，後者等待 factorial(1)，後者等待 factorial(0)——然後答案沿著鏈往回展開。

為什麼重要與誠實的提醒：遞迴對自然自相似的問題——樹、巢狀結構、分治演算法——比迴圈表達得清楚得多。但每個待處理的呼叫都消耗一個堆疊框，所以漏掉或寫錯基底情況、或單純遞迴得太深，都會把呼叫堆疊撐爆而當掉（堆疊溢位）。遞迴也不是免費的：在 C 中，迴圈往往比深層遞迴便宜，因為它避免了每次呼叫的額外開銷與堆疊成長。