為什麼一個函式光靠暫存器不夠
在前兩篇導覽裡，我們把運算式、分支、迴圈與指標存取，翻譯成了純粹的組合語言。每個值都住在那一小撮暫存器之一裡——在 RISC-V 上大概三十二個格子。對一段筆直的程式碼來說，這很夠用。但真正的程式是一棵互相呼叫的函式之樹：main 呼叫 parse、parse 呼叫 read、read 又呼叫一個小幫手，而它們每一個，都想拿那同樣的三十二個暫存器來做自己的事。parse 一呼叫 read，read 就會踩爛 parse 還在用的那些暫存器。我們需要一個地方，能把東西放下，等控制權回來時，再原封不動地拿回來。
這裡藏著一個更深的問題，正是它讓「只靠暫存器」變得無望。函式呼叫像俄羅斯娃娃一樣層層巢狀，並以嚴格的「後進先出」順序解開：最晚被呼叫的函式，永遠最先結束並返回。我們拿來存放、復原暫存器的那個結構，最好能精準地照著這套紀律——進入函式時長大、離開時縮小、而且永遠最先釋放最新放進去的東西。那個結構就是堆疊，正是這一個想法，把一堆固定的暫存器，變成一台能跑任意深度程式的機器。
堆疊：一根插著便條紙的釘子
想像書桌上有一根老式的釘子，你把待會兒可能要拿回來的便條紙插上去。你永遠把最新的便條加在最上面，也永遠最先把最頂上那張抽走——後進先出。堆疊正是這個樣子，只不過是從一般記憶體裡切出來的。硬體沒替它變什麼魔術；訣竅在於有一個暫存器，也就是堆疊指標，單純地記著這根釘子頂端的位址。要用堆疊，你永遠只動這一個暫存器，並讀寫它所指位置附近的記憶體。
依照慣例，堆疊往下生長——朝著較小的位址。要挪出比方說 16 位元組的暫存空間，你就把堆疊指標減去 16；要把那塊空間還回去，就加上 16。「推入」（push）就是把指標減小再寫入；「彈出」（pop）就是讀取再把指標加回去。一開始會覺得上下顛倒，但這規則從不改變，而那一個移動的指標，就是整套記帳系統。它底下的一切，是某個函式宣告擁有的、活著的暫存空間；最初起點之上的一切，則是呼叫者的世界，原封不動地等著。
返回位址：函式如何找到回家的路
當你呼叫一個函式，你是刻意地把程式計數器交出去——叫機器跑去執行別處的程式碼。明顯的問題是：它到底怎麼回得來？答案是返回位址，也就是那條呼叫指令正後方那條指令的位址。一次呼叫同時做兩件事：它存下那個返回位址，再把程式計數器設成函式的起點。函式做完後，把存下的位址載回程式計數器，執行便精準地從呼叫者離開的地方繼續——就像一張書籤，讓你晃進一條註腳，再回到你原本正在讀的那個字。
RISC-V 的呼叫指令 jal（jump-and-link，跳躍並連結）把這點表現得很漂亮：它一步之內就跳到目標並且把返回位址寫進一個暫存器（那個「連結」暫存器）。返回於是不過就是跳回那個暫存器所存的位址。但一個暫存器只能存一個返回位址——那麼當被呼叫的函式又去呼叫另一個函式、把它蓋掉時，會發生什麼事？這又是巢狀問題，而解藥就是堆疊：一個自己也要發出呼叫的函式，必須先把它寶貴的返回位址推入堆疊妥善保管，再在返回前一刻把它彈回來。
堆疊框架：一個函式，一張工作台
每一次函式呼叫，都會在堆疊上切出一塊自己的連續區段——它的堆疊框架——並在這次呼叫期間，把它當成一張私人工作台。框架是這個函式為了熬過一次巢狀呼叫所需的一切之天然居所：存下的返回位址、它必須保住的暫存器、塞不進暫存器的區域變數（比方說一個陣列或一個結構），以及正要往下傳的引數。當函式返回時，它一口氣把框架的大小加回堆疊指標，整張工作台便消失無蹤，留下呼叫者的框架，原原本本如初。
通常還有第二個暫存器，叫做框架指標，會在進入時停泊在框架固定的底座上。既然堆疊指標已經標出了頂端，何必多此一舉？因為堆疊指標在函式執行中可能一直移動（為後續呼叫推入引數），所以從它量起的距離會跟著飄。框架指標則牢牢釘在一個位置，讓每個區域變數都有一個固定、永不改變的位移——對編譯器與真人除錯者來說，都好推理得多。它是選用的：最佳化編譯器常常把它丟掉以空出一個暫存器，改從那個移動中的堆疊指標來算區域變數的位移。
high addresses +------------------------+ | caller's frame ... | +------------------------+ <- frame pointer (fixed base of this frame) | saved return address | | saved registers | | local array[ ] | | outgoing arguments | +------------------------+ <- stack pointer (top; moves during the call) low addresses (stack grows downward, toward smaller addresses)
引數，以及呼叫者與被呼叫者的協定
呼叫一個函式，意味著把輸入交給它、再拿回一個結果，而大家必須對這些值住在哪裡有共識——哪個暫存器存第一個引數、哪個存返回值。這份共識，是我們下一篇導覽要深入研究的呼叫慣例的一部分。快路徑是暫存器：頭幾個引數搭在指定的暫存器上、結果也從一個指定的暫存器送回來，完全不必碰記憶體。只有當引數比約定的暫存器還多、或某個引數太大時，呼叫者才會把溢出的部分溢寫到堆疊上。
還剩下那個踩踏問題：函式執行時會自由地使用暫存器，而其中有些暫存器，存著呼叫者還在乎的值。慣例用一份乾淨的條約解決它，把暫存器分成兩個陣營。呼叫者保存（caller-saved）的暫存器是可以隨便動的——函式可以把它們蓋掉，所以呼叫者若想讓某個值熬過一次呼叫，它自己得先存起來。被呼叫者保存（callee-saved）的暫存器則帶著一個承諾：用到它的函式，必須在返回前把它原本的值復原，這樣呼叫者就能信任這些值跨越呼叫後仍完好。這份分工意味著哪一方都不必存下全部，只存自己約定的那一份——而當真要存時，就存在堆疊框架上。
遞迴：同一份程式碼，許多框架
現在收割成果。一個遞迴函式呼叫它自己，而堆疊讓這件事感覺幾乎稀鬆平常。每一次呼叫都拿到自己嶄新的框架——自己的一份區域變數副本與返回位址——疊在它父輩的框架之上。看 factorial(3)：對 factorial(3) 的呼叫推入一個框架，接著呼叫 factorial(2) 又推入一個，後者再呼叫 factorial(1) 推入第三個。堆疊此刻存著同一份程式碼的三個獨立框架，每個都記著自己的 n 以及要返回哪裡。隨著每個觸底或已完成的呼叫返回，它的框架便彈出，答案順著父輩一路往上流回，恰好倒轉了它們被推入的次序。
- 呼叫 factorial(3)：推入一個存著返回位址與 n=3 的框架；因為 3 不是基底情形，呼叫 factorial(2)。
- 呼叫 factorial(2)：推入第二個存著 n=2 的框架；不是基底情形，於是呼叫 factorial(1)。堆疊此刻有兩個框架。
- 呼叫 factorial(1)：推入第三個存著 n=1 的框架；這正是基底情形，於是返回 1，並彈出這個框架。
- 回到 factorial(2)：算出 2 x 1 = 2，返回 2，彈出它的框架。回到 factorial(3)：算出 3 x 2 = 6，返回 6，彈出。堆疊清空，答案是 6。
這正是為什麼遞迴不需要特殊硬體：它不過是把那套普通的呼叫－返回機制，套用在同一個函式上，由堆疊默默地替每一個活著的呼叫各撐一個框架。它也揭露了代價。每一次呼叫都吃掉更多堆疊，而堆疊是有限的——一個沒有可達基底情形的失控遞迴，會不斷推入框架，直到衝出尾端，也就是那令人聞之色變的堆疊溢位（stack overflow）。堆疊是那個優雅、有界的資源，把一組固定的暫存器變成一台無限深度的機器，但有界就是有界：深度仍有天花板。