遞迴
遞迴，是指一個函式透過在「同一個問題的更小版本」上呼叫自己來求解。腦海裡可以想像一組俄羅斯套娃：要打開最大的娃娃，就得打開裡面那個稍小一點的，而它裡面又套著更小的，直到最小那個一打開裡面什麼也沒有。那個最小的娃娃正是關鍵所在——每一段正確的遞迴都有一個基準情形（base case），即簡單到無需再呼叫就能直接給出答案的情況；以及一個遞迴情形，它做一點點工作，再把剩下的交給更小的一次呼叫。「4 的階乘是多少？」變成「4 乘以 3 的階乘」，再變成「4 乘 3 乘 2 的階乘」，如此一路降到 0 的階乘——我們直接規定它等於 1。
從機制上看，每一次呼叫都有自己的小工作區——它自己的那一份區域變數——一層層疊放在前一次呼叫之上，存放在記憶體中一塊叫做呼叫堆疊（call stack）的區域。電腦一路向下俯衝，堆起一串未完成的呼叫，直到撞上基準情形；接著開始回捲，沿途逐一完成每一個擱置的呼叫，把答案交還給正在等待它的那一層。如果你忘了寫基準情形（或者根本沒有朝它靠近），堆疊就會不斷增長，直到程式以堆疊溢位（stack overflow）崩潰——這正是遞迴最出名的失敗方式。
遞迴是一種思維方式，並非免費的午餐。樸素的遞迴可能把同一個子問題反反覆覆地重算：用最直白的兩路遞迴去算第 n 個費氏數會指數級分叉，本該只需 O(n) 的事情卻做了大約 O(2^n) 的工作。補救之道，要麼記住已經算過的答案（記憶化 memoization），要麼把遞迴翻轉成一個自底向上填表的迴圈（動態規劃 dynamic programming）。遞迴也是分治法以及走訪樹、圖結構最自然的表達語言。
int fib(int n) {
if (n < 2) return n; // base case
return fib(n - 1) + fib(n - 2); // recursive case (branches!)
}
// fib(4)
// / \
// fib(3) fib(2)
// / \ / \
// fib(2) fib(1) fib(1) fib(0)
// / \
// fib(1) fib(0)同一個子問題出現在多個分支上——這正是記憶化要消除的浪費。
原則上，每一段遞迴都能用一個顯式的堆疊改寫成迴圈，反之亦然。某些語言會優化一種特例——尾遞迴，即遞迴呼叫是函式做的最後一件事——把它變成不耗費額外堆疊空間的普通迴圈；C++ 編譯器可能這樣做，但並不保證，所以別指望靠它來支撐無限深度。