堆疊上的遞迴

遞迴是一個函式藉由對同一問題的較小版本呼叫自己來解題，就像一組層層相套的俄羅斯娃娃：打開一個，裡面又有一個一模一樣的，直到抵達中心那個小小的實心娃娃。把 factorial(4) 說成等於 4 乘以 factorial(3)、後者又等於 3 乘以 factorial(2)、依此類推，這就是遞迴。自然會問：同一個函式怎麼能同時跑很多次，而它那許多份 i 和 n 卻不會糾纏在一起？

答案是堆疊。每一次對該函式的呼叫都搭建自己全新的堆疊框，帶著自己私有的引數與區域變數副本，疊在發起它的那個呼叫的框之下。隨著遞迴往下走，框一層層堆高；每一個都記著自己的返回位址與自己的資料。當終於抵達基本情況（那個打不開的娃娃），這些呼叫就一個接一個返回，每個框被拆除，控制流沿著堆疊往回展開，並在退出途中把結果組合起來。堆疊指標先往下、再爬回去，正是「往深處走、再返回」的實體軌跡。

堆疊上的遞迴之所以重要，是因為它顯示堆疊不只是記帳；它正是讓每次呼叫都擁有自己一方天地的東西。它也揭示了成本：每一層深度都吃掉一個框，所以無界遞迴（基本情況遺漏或寫錯）會不斷配置框，直到衝出保留的堆疊區域，這就是堆疊溢位。這正是為什麼在堆疊空間吃緊處，深度遞迴會很危險；也是為什麼有些編譯器會把一種特例——尾遞迴（tail recursion）——轉成一個重用單一框的普通迴圈，而不是讓堆疊不斷成長。