遞迴
當一個函式會呼叫自己時，它就是遞迴的。
呼叫函式與迴圈的一個關鍵差異在於，呼叫函式會把要返回的位址推入堆疊。
這表示遞迴函式通常比等效的迴圈需要更多堆疊空間。
因此，一個不斷呼叫自己的函式最後可能會耗盡所有堆疊空間。
這種情況稱為堆疊溢位。
這就是為什麼每個遞迴函式都必須至少有一個基本情況，也就是函式不呼叫自己就直接回傳的情況。
任何遞迴呼叫最終都必須抵達基本情況。
例如，階乘函式n! = n * (n - 1) * ... * 1可以用1作為基本情況，以遞迴方式定義：
factorial:
; the argument `n` is passed on `rdi`
; the factorial will be returned on `rax`
cmp rdi, 1
jle .base_case ; base case -> if rdi <= 1, return 1
push rdi ; save n
dec rdi ; rdi = n - 1
call factorial ; recursive call, rax = (n - 1)!
pop rdi ; restore n
imul rax, rdi ; rax = n * (n - 1)! = n!
ret
.base_case:
mov rax, 1
ret
注意，factorial必須在遞迴之前push rdi，並在之後pop rdi。
這是因為遞迴呼叫回傳之後，它仍然需要n才能計算n * (n-1)!。
另外也要注意，改用由被呼叫者負責儲存的暫存器並不能解決這個問題。
即使遞迴函式可能是自己的呼叫者，它本身也是其他某個函式的被呼叫者。
這表示函式在使用由被呼叫者負責儲存的暫存器之前，也必須先保存它們，並在使用之後還原它們的值。
這通常透過push/pop序列完成，就像我們在前一個概念中看過的那樣。
由於遞迴函式的每一層框架（基本情況除外）也都是需要保留自己區域變數的呼叫者，這個push/pop序列在每一層框架中都必須重複一次。
即使是直接把變數存進堆疊、不使用暫存器，每一層框架仍然要付出同樣的8位元組。
這表示每次遞迴呼叫都會因為call推入的返回位址而在堆疊上增加8位元組，再加上它需要保存的每個區域變數各8位元組。
函式會在每一層框架持續把這些位元組加到堆疊上，直到抵達基本情況為止。
直到那時，它才開始以相反順序逐層返回，每個遞迴呼叫视需要執行對應數量的pop，然後執行ret。
例如，如果以引數10呼叫factorial，它會在抵達基本情況1之前先呼叫自己 9 次。
在那個時候，已經用掉144位元組，用來儲存先前每一層框架的n（8位元組）以及返回位址（8位元組）。
尾呼叫
在某些情況下，函式在呼叫另一個函式之後、回傳之前，不會再做任何工作。
例如：
times_three:
imul rax, rdi, 3
ret
triple_of_square:
imul rdi, rdi
call times_three
ret
函式triple_of_square會：
- 把傳入的引數（位於
rdi）乘上自己，得到它的平方；
- 然後呼叫
times_three，它會回傳三乘上傳入的引數。
結果，triple_of_square會回傳3*x²，其中x是它的引數，透過rdi傳入。
注意，triple_of_square在呼叫times_three之後沒有做任何工作，只是直接回傳。
在這種情況下，函式可以改用jmp把執行轉移給被呼叫的函式，而不是使用call：
times_three:
imul rax, rdi, 3
ret
triple_of_square:
imul rdi, rdi
jmp times_three
這稱為尾呼叫。
尾呼叫的主要優點是省下call的額外成本。
call會把返回位址推入堆疊，而控制權要回到那一點，就必須有對應的ret。
尾呼叫把兩者都省掉了：沒有返回位址要推入，也沒有多餘的ret需要配對，只有被呼叫函式自己的ret。
尾遞迴
對於在回傳之前可能呼叫自己很多次的遞迴函式來說，尾呼叫特別有用。
不過，並不是每個遞迴呼叫都能直接轉換成尾呼叫。
由於jmp會把控制權轉移給被呼叫的函式，呼叫者在尾呼叫之後就無法再做任何工作。
例如，先前的factorial函式不是尾遞迴。
在遞迴呼叫之後，它仍然需要用imul rax, rdi把結果乘上目前的n。
在這種情況下，有時可以使用累加器來收集部分計算結果，並在最後回傳。
例如，我們可以定義一個負責大部分工作的factorial_helper，然後由factorial設定累加器並把控制權轉移給factorial_helper：
factorial_helper:
; the argument `n` is passed on `rdi`
; `rax` is used as an accumulator and will be returned at the end
cmp rdi, 1
jle .base_case
imul rax, rdi ; we accumulate the partial result on `rax`
dec rdi ; rdi = n - 1
jmp factorial_helper ; tail call to accumulate (n - 1)!
.base_case:
ret ; returns the factorial already accumulated on `rax`
factorial:
mov rax, 1 ; initial value for the accumulator
jmp factorial_helper ; tail call
由於遞迴呼叫之後不再做任何工作，我們也不再需要保存rdi。
沒有call也沒有push rdi，所以每次遞迴疊代都只在堆疊上增加0位元組：不會用到額外的堆疊空間。
這個版本可以處理任意大的n，而不會讓堆疊溢位。
它既更有效率，也更安全。
在某些情況下，調整函式的排列順序後，甚至連跳到輔助函式的jmp都可以省掉。
例如，factorial和triple_of_square可以改寫成這樣：
factorial:
mov rax, 1
factorial_helper:
cmp rdi, 1
jle .base_case
imul rax, rdi
dec rdi
jmp factorial_helper
.base_case:
ret
triple_of_square:
imul rdi, rdi
times_three:
imul rax, rdi, 3
ret
在上面的程式碼片段中，factorial的執行會直接往下進入factorial_helper。
triple_of_square與times_three也是如此。
在這兩種情況下，執行都依序繼續，看起來尾端的函式只是「主要」函式裡的區域標籤。
實際上，任何區域標籤和函式之間並沒有本質上的差異。
x86-64 組合語言不會對其中任何一個給予特殊待遇，它們都只是可執行程式碼區段中的位址，例如section .text。
這樣一來，尾遞迴函式基本上可以想成和迴圈一樣：遞迴呼叫會跳回頂端，而基本情況就是結束迴圈的條件。
學習練習
