递归
当一个函数调用自身时，它就是递归的。
函数调用和循环的一个关键区别在于：调用函数会把返回地址压入栈。这意味着递归函数通常比等价的循环需要更多的栈空间。
因此，一个不断调用自身的函数最终可能会耗尽所有栈空间。这称为栈溢出。
这就是为什么每个递归函数都必须至少有一个基本情况：函数不再调用自身、直接返回的那种情况。任何递归调用最终都必须到达某个基本情况。
例如，阶乘函数 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-1)! 仍然需要 n。
另请注意，使用被调用者保存寄存器并不能解决这个问题。
尽管递归函数可能是自身的调用者，但它同时也是其他某个函数的被调用者。这意味着该函数在使用被调用者保存寄存器之前，也必须先保存它们，并在使用之后恢复它们的值。这通常通过 push/pop 序列来完成，我们在之前的概念中已经见过。
递归函数的每一帧（基本情况除外）也都是一个调用者，需要保存自己的局部变量，因此这个 push/pop 序列必须在每一帧重复。即使不通过寄存器、而是直接把变量存到栈上，每一帧仍然要花费同样的 8 字节。
这意味着每次递归调用都会为 call 压入的返回地址向栈上添加 8 字节，再为它需要保存的每个局部变量添加 8 字节。函数会在每一帧不断向栈上添加这些字节，直到到达基本情况。只有到了那时，它才开始按相反的顺序展开，每个递归调用按需执行若干次 pop，然后执行一次 ret。
例如，如果以实参 10 调用 factorial，它会在到达 1 这个基本情况之前调用自身九次。到那时，已经用了 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 之后不再做任何工作，函数直接返回。在这种情况下，函数可以不用 call，而是用 jmp 把执行转移给被调用的函数：
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 那样包含可执行代码的段中的地址。
这样看来，尾递归函数基本上可以看作是一个循环：递归调用跳回顶部，而基本情况则是结束循环的条件。
学习练习
