汇编：调用向下展开，结果逐层返回

到了汇编层，递归仍然不是一条特殊指令。每次自调用都执行普通的 call：CPU 保存返回位置，被调用函数建立一份新栈帧，完成后再用 retq 回到上一层。

第五章汇编生成器真正新增的算术动作只有 sub1 对应的 subq。递归本身复用了第四章已经建立的函数地址、参数寄存器、间接调用和返回值约定。

先生成完整汇编

运行：

1
2
3

cd code/05_recursion
make
./mini compile examples/recursive_sum.lang -o out.s

在 macOS 上，文件开头是 _main；在 Linux 和 WSL 上则是 main。默认情况下，编译器会根据自身运行的平台选择入口名字；--target 也可以覆盖这项符号约定，但不会把汇编改成另一种 CPU 指令集。后文省略入口拼写差异，重点观察递归函数的局部标签 .Llambda0。

sub1 变成一次减法

汇编生成器处理 OpKind::sub1 的代码是：

1
2
3
4
5

case OpKind::sub1:
    out_ += "    movq " + operand_text(op.lhs) + ", %rax\n";
    out_ += "    subq $1, %rax\n";
    out_ += "    movq %rax, " + stack_slot(op.dst) + "\n";
    return;

对于 IR：

1

t.2 = sub1 n

生成的汇编是：

1
2
3

movq -8(%rbp), %rax
subq $1, %rax
movq %rax, -40(%rbp)

-8(%rbp) 是当前调用的参数 n，-40(%rbp) 是临时值 t.2 的栈槽。subq 修改的是 %rax 中的副本，不会覆盖本层保存的 n；递归调用返回后，本层还要用原来的 n 做加法。

主程序和函数体各自取得同一个地址

主程序中的 IR：

1

f.0 = function lambda0

生成：

1
2

leaq .Llambda0(%rip), %rax
movq %rax, -8(%rbp)

函数体中的 IR：

1

sum0 = function lambda0

也生成一次：

1
2

leaq .Llambda0(%rip), %rax
movq %rax, -16(%rbp)

两次 leaq 计算的是同一个 .Llambda0 地址，但保存位置属于不同栈帧：

这里两个 %rbp 也不是同一个值。执行主程序时，它指向 main 的栈帧；执行递归函数时，它指向当前这一层函数调用的栈帧。

main 发起第一次调用

贯穿示例的 main 部分是：

1
2
3
4
5
6
7
8
9

pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
leaq .Llambda0(%rip), %rax
movq %rax, -8(%rbp)
movq -8(%rbp), %rcx
movq $5, %rdi
call *%rcx
movq %rax, -16(%rbp)

这与第四章的普通函数调用相同：

1
2
3
4

%rcx = callee 的代码地址
%rdi = argument 5
call *%rcx
%rax = 调用返回值

虽然编译器知道这个地址最初来自 .Llambda0，IR 的 callee 仍然是一个普通函数值。汇编生成器因此继续使用间接调用 call *%rcx，没有为递归另开一套直接调用规则。

每次进入函数都会建立新栈帧

递归函数从同一个标签开始：

1
2
3
4
5

.Llambda0:
    pushq %rbp
    movq %rsp, %rbp
    subq $64, %rsp
    movq %rdi, -8(%rbp)

每次执行到 .Llambda0 都会重新运行这段序言：

1. 保存上一层的 %rbp；
2. 让 %rbp 指向这一层的栈帧；
3. 为这一层的局部槽留出 64 字节；
4. 把这一层收到的参数保存到自己的 n 槽。

recursive_sum.lang 的函数体一共需要七个槽：

七个槽需要 56 字节，emitter 把局部区向上对齐到 64 字节。不同递归层使用相同的偏移，但各自的 %rbp 不同，所以 sum(5) 的 -8(%rbp) 保存 5，sum(4) 的同一偏移保存 4，互不覆盖。

条件决定是否继续向下调用

函数先保存 self 地址，再检查基例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

leaq .Llambda0(%rip), %rax
movq %rax, -16(%rbp)
movq -8(%rbp), %rax
cmpq $0, %rax
sete %al
movzbq %al, %rax
movq %rax, -24(%rbp)
movq -24(%rbp), %rax
cmpq $0, %rax
je .Lelse0

条件为真时，执行顺序直接进入紧跟其后的 then 块：

1
2
3
4

.Lthen0:
    movq $0, %rax
    movq %rax, -32(%rbp)
    jmp .Lend0

这就是 sum(0) 的停止路径。它不再执行 call，而是把本层结果设为 0。

条件为假时，跳到 else 块，把参数减一并发起递归调用：

1
2
3
4
5
6
7
8

.Lelse0:
    movq -8(%rbp), %rax
    subq $1, %rax
    movq %rax, -40(%rbp)
    movq -16(%rbp), %rcx
    movq -40(%rbp), %rdi
    call *%rcx
    movq %rax, -48(%rbp)

当 n 是 5 时，这次调用把 4 放进 %rdi。新一层进入 .Llambda0 后会建立自己的栈帧，再把 4 保存到那一层的 -8(%rbp)。

调用链怎样向下展开

执行 (sum 5) 时，尚未完成的栈帧依次增加：

1
2
3
4
5
6
7

main
└── sum(5)，等待 sum(4)
    └── sum(4)，等待 sum(3)
        └── sum(3)，等待 sum(2)
            └── sum(2)，等待 sum(1)
                └── sum(1)，等待 sum(0)
                    └── sum(0)，命中基例

每条 call *%rcx 还会把“返回后从哪条指令继续”压到栈上。加上函数序言保存的旧 %rbp，运行到最深处时，栈中同时存在 main 和六次 sum 调用的状态。

这解释了递归为什么需要独立栈帧：sum(5) 在等待时必须保留自己的 n == 5，否则更深层返回后就不知道该加上哪个数。

结果怎样逐层回卷

sum(0) 把 0 放进结果槽，随后执行：

1
2
3
4
5

.Lend0:
    movq -32(%rbp), %rax
    movq %rbp, %rsp
    popq %rbp
    retq

%rax 携带返回值，retq 取出最近一次 call 保存的返回地址，回到上一层 call *%rcx 后面的指令。上一层先保存这个结果，再完成尚未执行的加法：

1
2
3
4

movq %rax, -48(%rbp)
movq -8(%rbp), %rax
addq -48(%rbp), %rax
movq %rax, -56(%rbp)

于是返回过程是：

最后 15 回到 main 的 %rax，被保存到 main 的调用结果槽，再作为整个程序的结果返回。

递归调用前仍然满足栈对齐

System V x86-64 调用约定要求调用点的 %rsp 保持 16 字节对齐。进入函数时，返回地址已经让 %rsp 相对 16 字节边界偏移 8 字节；序言中的：

1

pushq %rbp

再使用 8 字节，使 %rsp 回到 16 字节边界。随后 main 减去 16 字节，递归函数减去 64 字节，它们都是 16 的倍数。因此 main 的第一次调用和函数体内每一次递归调用，都在相同的对齐条件下执行。

递归层数增加不会改变这条推理：每一层都执行同样的序言，并在返回前用同样的尾声恢复栈。

尾位置也不会自动变成跳转

examples/countdown.lang 的递归分支是：

1

(down (sub1 n))

它的结果会直接成为当前函数结果，调用之后没有加法。运行：

1
2

./mini run examples/countdown.lang
./mini ir examples/countdown.lang

解释器得到 42，IR 的 else 块包含：

1
2
3

t.2 = sub1 n
t.3 = call down0 t.2
t.1 = t.3

虽然这次递归调用位于尾位置，当前后端仍然生成：

1
2
3
4

call *%rcx
movq %rax, -48(%rbp)
movq -48(%rbp), %rax
movq %rax, -32(%rbp)

也就是说，每次 down 仍建立新栈帧，并在返回后经过当前函数的尾声。第五章不把尾位置的 call 改写成 jmp；普通调用与递归调用继续共用同一条生成路径。

链接并观察结果

在 x86-64 Linux、WSL 或 Intel Mac 上：

1
2
3
4

./mini compile examples/recursive_sum.lang -o out.s
cc out.s -o out
./out
echo $?

预期看到：

1

15

程序本身没有打印一行 15；这里显示的是 echo $? 读取到的进程退出状态。

Apple Silicon Mac 上，cc 默认目标通常是 arm64，而本课程生成的是 x86-64 汇编。需要让汇编和链接都选择 x86-64：

1
2
3
4

./mini compile examples/recursive_sum.lang -o out.s
cc -arch x86_64 out.s -o out
./out
echo $?

如果本机缺少对应工具链或 Rosetta，可以在 x86-64 Linux、WSL 或 Intel Mac 环境完成这一步。

shell 的进程退出状态只能方便地观察 0 到 255。本例结果 15 正好落在这个范围内；更大的合法计算结果应使用：

1

./mini run program.lang

直接查看解释器输出。第四章末尾的 cin、cout 和 C++ runtime 联调是一次性实验，不属于第五章代码快照；本章仍用解释器输出或小整数退出状态检查结果。

到这里，机器侧的递归路径已经闭合：

1
2
3
4
5

同一函数标签
-> 每层取得 self 地址
-> call 建立下一层
-> 基例停止
-> %rax + retq 逐层返回