為什麼函式需要一份條約
在上一篇裡，一次程序呼叫跳離原地，再由返回位址把它帶回家。但真正的程式是一大群函式，許多出自素未謀面的人之手，分別編譯，甚至相隔多年。當你的程式碼呼叫一個函式庫例程時，引數該擺在哪？這個例程可以隨意塗改哪些暫存器，又必須原封不動地交還哪些？如果每個人各自猜測，什麼都接不起來。解法就是呼叫慣例：一份為某個 ISA 寫定一次的條約，每個編譯器、每個寫組合語言的人都同意遵守。
把它想成預約一間給陌生人共用的會議室。條約說：把你的訊息留在門邊這幾個指定的標籤上（引數暫存器），回覆要放的房號擺在這裡（返回值暫存器），而白板上你看到的任何東西，要嘛保持原樣，要嘛先拍照、離開前再復原。慣例不是矽片的一部分——硬體很樂意讓你違反它——但只要你違反，回到的就會是一個狀態已被悄悄毀掉的呼叫者。
誰來存誰：呼叫者與被呼叫者
條約裡最鋒利的一條，把暫存器檔分成兩個陣營。有些暫存器是呼叫者保存（又稱揮發性或暫用）：被呼叫的函式可以任意覆寫它們，所以呼叫者若還需要那裡的值，就得在呼叫前把它溢出到堆疊、呼叫後再載回來。另一些是被呼叫者保存（保留）：想用其中一個的函式，必須先存下舊內容、返回前再復原，好讓呼叫者看到的它原封不動。整套呼叫者與被呼叫者保存的劃分，是一樁關於「誰來付出保存代價」的精打細算。
為什麼要這樣劃分，而不乾脆每次都把全部存起來？因為存就是工——每一次溢出都是一次記憶體儲存。劃分讓兩邊都只存自己真正在乎的東西。一個跨呼叫並未握有任何重要值的呼叫者，什麼都不必存；一個只需要暫用暫存器的葉子函式，也什麼都不必存。慣例之所以這樣切，是為了讓平均而言發生的儲存與載入最少。這是結構界「讓常見情況變快」這句箴言的一個小小實例。
堆疊框架：每次呼叫一個房間
每一個進行中的呼叫，都拿到自己一塊私有的堆疊記憶體，叫做堆疊框架（或稱啟動紀錄）。進入一個函式時，它把堆疊指標往下推一個固定的量，鑿出空間來放它要保存的暫存器、它的區域變數，以及任何它得繼續往下傳的引數。返回時，它把同樣的量彈回去，把那個房間抹得彷彿從未存在。一層層疊上去的框架鏈，其實就是程式「誰呼叫了誰」這段歷史，凍結在記憶體裡。
許多慣例還會保留一個框架指標——第二個暫存器，釘在目前框架的起點，而堆疊指標則隨著函式推入彈出而四處游移。框架指標一旦固定，每個區域變數都落在距它一個固定偏移量的位置，這讓除錯器與堆疊追蹤好走得多。最佳化編譯器常常捨棄框架指標來騰出那個暫存器、改從堆疊指標算偏移；那樣較快，卻也正是某些最佳化過的當機傾印難讀的原因。
high addresses +---------------------+ | caller's frame | +---------------------+ <- frame pointer (fp) | saved return addr | | saved callee regs | | local variables | | outgoing arguments | +---------------------+ <- stack pointer (sp), grows downward low addresses
遞迴不過是框架一層層疊起來
重點來了。遞迴看起來很神秘——一個函式呼叫自己——但對堆疊來說它一點都不特別。每一次呼叫都只是拿到自己一塊嶄新的堆疊框架，裡頭有它私有的區域變數副本，以及它自己存下的返回位址。函式不知道、也不在乎呼叫它的剛好是自己的另一份副本。堆疊上的遞迴能行得通，理由和一次普通呼叫一模一樣：每一次啟動都被分開記帳。
- 呼叫 factorial(3)。推入一個框架，存著 n=3 與返回原呼叫者的返回位址。
- 因為 n 不是 1，它呼叫 factorial(2)。第二個框架疊在上面，存著 n=2 與指回 factorial(3) 的返回位址。
- factorial(2) 呼叫 factorial(1)。第三個框架，n=1，返回位址指回 factorial(2)。堆疊現在疊了三層。
- factorial(1) 碰到基底情形，返回 1，彈掉自己的框架。控制權沿著返回位址回到 factorial(2)。
- 每個框架依序回收：factorial(2) 算出 2 x 1 = 2 後返回；factorial(3) 算出 3 x 2 = 6 後返回。堆疊再次清空，手裡握著答案 6。
請注意，硬體裡沒有任何東西「知道」什麼是遞迴。堆疊指標只是不斷往下走、再走回來，而存下的那些返回位址，組成一條一次一步把人帶回家的麵包屑路徑。遞迴唯一消耗的資源是堆疊空間——每個尚未完成的呼叫一個框架。遞迴得太深，你就會把堆疊區耗盡：那就是令人聞風喪膽的堆疊溢位，也是為什麼無止境的遞迴會當機，而不是永遠跑下去。
誠實的提醒與更大的圖像
幾點誠實的但書。第一，確切的慣例——哪些暫存器帶引數、超過幾個才溢出到堆疊、結構體怎麼傳——會因 ISA 而異，甚至同一個 ISA 在不同作業系統上也不同，這正是為什麼一份 x86-64 的 Linux 二進位檔，沒辦法直接呼叫一個 Windows 函式。原則是放諸四海皆準的；門上那些具體的標籤則不是。第二，遞迴雖優雅卻不免費：每個框架都耗記憶體、外加幾次儲存與載入，所以一段深遞迴，可能比一個結果相同的等價迴圈更慢、更吃記憶體。編譯器有時會用「重複利用同一個框架」來搭救尾遞迴，但你不能指望它一定會。
退一步看看，用了多麼少的東西就搭出了多麼多的功能。堆疊不過是記憶體加一個指標；慣例不過是一份約定；遞迴不過是一層層框架。然而它們合在一起，就讓陌生人寫的程式碼能彼此合作、讓函式能任意巢狀深入、讓一個自我指涉的定義算出一個具體的答案。下一篇將離開執行中的程式，回頭問：這些分別編譯的片段一開始究竟是怎麼被黏在一起的——也就是連結器與載入器——以及一個程式最終如何透過系統呼叫和作業系統對話。