堆疊與遞迴（the stack and recursion）

為什麼堆疊是遞迴背後的資料結構？因為遞迴與堆疊有相同的形狀：最近開始的東西必須最先結束。當函數 f 呼叫 g，g 又呼叫 h，你必須等 g 返回才能從 f 返回，必須等 h 返回才能從 g 返回。這種後進先出的紀律正是堆疊所強制的——所以追蹤待處理呼叫的機制就直接被叫做呼叫堆疊（call stack）。

用淺白的步驟來看這個機制。程式每次進入一個函數，就在呼叫堆疊上推入一個框架（frame），裡面裝著返回位址與該函數的區域變數。函數每次返回，就把那個框架彈出，恢復呼叫者的狀態。由於推入與彈出總是碰最上面，最深層的巢狀呼叫永遠是當前正在處理的那一個，而這條鏈以完美的相反順序逐層收回。同樣的想法可用來求值算術表達式：要計算 (3 + 4) * 5，你推入部分結果與運算子，並在解決每個括號片段時彈出它們——巢狀結構由堆疊處理。

這是整個領域具體、日常的面貌。下推自動機之所以是「有限控制加一個堆疊」，正是因為巢狀、遞迴的結構——配對括號、巢狀區塊、遞迴的文法規則——是單一堆疊能追蹤、而有限記憶體不能的東西。當編譯器以遞迴下降剖析一個遞迴定義的文法時，程式自身的呼叫堆疊「就是」PDA 的堆疊。所以抽象理論與真實程式的執行期行為，是同一台機器的兩種觀點：一個由後進先出記憶體支撐的有限控制器。