3.7.6 递归过程

前面已经描述的寄存器和栈的惯例使得 x86-64 过程能够递归地调用它们自身。每个过程调用在栈中都有它自己的私有空间，因此多个未完成调用的局部变量不会相互影响。此外，栈的原则很自然地就提供了适当的策略，当过程被调用时分配局部存储，当返回时释放存储。

图 3-35 给出了递归的阶乘函数的 C 代码和生成的汇编代码。可以看到汇编代码使用寄存器 %rbx 来保存参数 n，先把已有的值保存在栈上（第 2 行），随后在返回前恢复该值（第 11 行）。根据栈的使用特性和寄存器保存规则，可以保证当递归调用 rfact(n-1) 返回时（第 9 行），（1）该次调用的结果会保存在寄存器 %rax 中，（2）参数 n 的值仍然在寄存器 %rbx 中。把这两个值相乘就能得到期望的结果。

从这个例子我们可以看到，递归调用一个函数本身与调用其他函数是一样的。栈规则提供了一种机制，每次函数调用都有它自己私有的状态信息（保存的返回位置和被调用者保存寄存器的值）存储空间。如果需要，它还可以提供局部变量的存储。栈分配和释放的规则很自然地就与函数调用-返回的顺序匹配。这种实现函数调用和返回的方法甚至对更复杂的情况也适用，包括相互递归调用（例如，过程 P 调用 Q，Q 再调用 P）。

long rfact(long n)
{
    long result;
    if (n <= 1)
        result = 1;
    else
        result = n * rfact(n-1);
    return result;
}

a) C 代码

long rfact(long n)
n in %rdi
1  rfact:
2      pushq %rbx             Save %rbx
3      movq %rdi, %rbx        Store n in callee-saved register
4      movl $1, %eax          Set return value = 1
5      cmpq $1, %rdi          Compare n:1
6      jle .L35               If <=, goto done
7      leaq -1(%rdi), %rdi    Compute n-1
8      call rfact             Call rfact(n-1)
9      imulq %rbx, %rax       Multiply result by n
10 .L35:                      done:
11     popq %rbx              Restore %rbx
12     ret                    Return

b) 生成的汇编代码

图 3-35　递归的阶乘程序的代码。标准过程处理机制足够用来实现递归函数

练习题 3.35 一个具有通用结构的 C 函数如下：

long rfun(unsigned long x) {
    if (________________)
        return ________________;
    unsigned long nx = ________________;
    long rv = rfun(nx);
    return ________________;
}

GCC 产生如下汇编代码：

long rfun(unsigned long x)
x in %rdi
1  rfun:
2      pushq %rbx
3      movq %rdi, %rbx
4      movl $0, %eax
5      testq %rdi, %rdi
6      je .L2
7      shrq $2, %rdi
8      call rfun
9      addq %rbx, %rax
10 .L2:
11     popq %rbx
12     ret

A. rfun 存储在被调用者保存寄存器 %rbx 中的值是什么？

B. 填写上述 C 代码中缺失的表达式。