递归的汇编实现
函数调用自身看起来像"自我循环"——栈帧机制让它成为可能。每调用一次自己，栈上就多一层帧，返回时再从最内层逐层弹出
函数能调用自己吗？
在 C 语言里写递归很简单：int fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
但汇编里没有”递归”这个语法——只有 CALL 和 RET。那递归是怎么工作的？
答案就在栈里。 每次调用自己，栈上就多一层栈帧。每层帧保存了不同的参数值和局部变量——它们互不干扰。
类比：俄罗斯套娃
俄罗斯套娃一层套一层，每一层的长相都一样，但大小不同：
- 最外层最大（n = 3）
- 往里一层小一点（n = 2）
- 最里层最小（n = 1）
- 打开最里层后，按原路一层层合回去
递归函数调用正是这样——每层调用有不同的参数，最深的那层返回后，结果一层层往回传。
从数学定义说起
阶乘（Factorial）是经典的递归例子：
n! = n × (n-1) × (n-2) × ... × 1
数学定义：
0! = 1
n! = n × (n-1)! （当 n > 0）
看，n! 的定义用到了 (n-1)!——函数用到了自己。这就是递归。
int fact(int n) {
if (n <= 1) return 1; // 基本情况（base case）
return n * fact(n - 1); // 递归情况（recursive case）
}
汇编实现：fact(3)
; 计算 fact(3) = 3 × 2 × 1 = 6
; 按照 cdecl 调用约定
_main:
PUSH #3 ; 参数 n = 3
CALL _fact
ADD SP, #4 ; 清理参数
; R0 = 6（返回值）
_fact:
; 序言
PUSH BP
MOV BP, SP
; [BP + 8] = n
; 判断基本情况：if (n <= 1) return 1
LOAD R0, [BP + 8] ; R0 = n
CMP R0, #1 ; n <= 1 ?
JLE _fact_base ; 是 → 返回 1
; 递归情况：return n * fact(n - 1)
LOAD R0, [BP + 8] ; R0 = n
SUB R0, #1 ; R0 = n - 1
PUSH R0 ; 参数：n - 1
CALL _fact ; 调用 fact(n - 1)
ADD SP, #4 ; 清理参数
; 此时 R0 = fact(n - 1)
LOAD R1, [BP + 8] ; R1 = n
MUL R0, R1 ; R0 = n * fact(n - 1)
JMP _fact_end ; 跳转到尾声
_fact_base:
MOV R0, #1 ; 基本情况：返回 1
_fact_end:
; 尾声
POP BP
RET
追踪执行过程：fact(3)
这是理解递归最关键的练习——让我们一步步跟踪栈的变化。
初始调用：_main 调用 _fact(3)
第 1 步：PUSH #3
栈： ┌──────────┐
│ n = 3 │ ← SP
└──────────┘
第 2 步：CALL _fact（压入返回地址）
栈： ┌──────────┐
│ n = 3 │
├──────────┤
│ 返回地址 │ ← SP
└──────────┘
第 3 步：进入 _fact，序言（PUSH BP, MOV BP, SP）
栈： ┌──────────┐
│ n = 3 │
├──────────┤
│ 返回地址 │
├──────────┤ ← BP（帧底）
│ 旧 BP │
└──────────┘ ← SP（帧顶）
第 4 步：n > 1，递归调用 _fact(2)
栈（此时有两层）：
┌──────────┐
│ n = 3 │ ← 第一层的参数
├──────────┤
│ 返回地址 │ ← 回 _main
├──────────┤ ← 第一层的 BP
│ 旧 BP │
├──────────┤ ← SP（第一层的栈顶）
│ n = 2 │ ← 第二层的参数（PUSH #2）
├──────────┤
│ 返回地址 │ ← 回第一层的 _fact
├──────────┤ ← 第二层的 BP
│ 第一层BP│ ← PUSH BP 保存的
└──────────┘ ← 第二层的 SP
第 5 步：n = 2 也大于 1，继续递归 _fact(1)
栈（三层了）：
┌──────────┐
│ n = 3 │
├──────────┤
│ 返回地址 │
├──────────┤
│ old BP │
├──────────┤
│ n = 2 │
├──────────┤
│ 返回地址 │
├──────────┤
│ old BP │
├──────────┤
│ n = 1 │ ← 第三层参数
├──────────┤
│ 返回地址 │ ← 回第二层
├──────────┤ ← 第三层 BP
│ old BP │
└──────────┘ ← 第三层 SP
第 6 步：n = 1，满足基本情况，返回 1
_fact(1) 执行：
R0 = 1 ← 基本情况
POP BP
RET ← 栈弹出，回到第二层
第 7 步：回到第二层（n = 2），计算 2 × fact(1)
恢复第二层上下文：
BP 恢复为第二层的帧底
从 [BP + 8] 读取 n = 2
R0 = fact(1) = 1
R1 = n = 2
R0 = 1 × 2 = 2
所以 fact(2) = 2
POP BP
RET ← 回到第一层
第 8 步：回到第一层（n = 3），计算 3 × fact(2)
从 [BP + 8] 读取 n = 3
R0 = fact(2) = 2
R1 = n = 3
R0 = 2 × 3 = 6
所以 fact(3) = 6
POP BP
RET ← 回到 _main
完整调用栈变化：
_main → fact(3) → fact(2) → fact(1) → return 1 → return 2 → return 6 → _main
┌──────┐ ┌──────┐ ┌──────┐
│ n=3 │ │ n=2 │ │ n=1 │
│ ... │ │ ... │ │ ... │
└──────┘ └──────┘ └──────┘
↓
栈深度 1 深度 2 深度 3 深度 2 深度 1
← 展开（回归）←
🔑 递归的精髓：每一层调用创建新的栈帧，参数不同但代码相同。最深的那层触发基本情况，开始逐层返回。后调用的先返回——栈的 LIFO 特性与递归天然匹配。
递归 vs 迭代
同样是计算阶乘，也可以用循环实现：
int fact_iter(int n) {
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
汇编对比
递归版本（我们已经写了）：
; 递归计算 fact(3)
; 需要 3 层栈帧，多次 CALL/RET
_fact_recursive:
PUSH BP
MOV BP, SP
LOAD R0, [BP + 8]
CMP R0, #1
JLE base_case
; ... 递归调用 ...
迭代版本：
; 迭代计算 fact(3)
; 只用有限的栈空间，一条直线执行
_fact_iter:
MOV R0, #1 ; result = 1
MOV R1, #2 ; i = 2
loop:
CMP R1, [BP + 8] ; i <= n?
JG done
MUL R0, R1 ; result *= i
ADD R1, #1 ; i++
JMP loop
done:
RET ; 返回 result
对比
| 方面 | 递归 | 迭代 |
|---|---|---|
| 空间 | 🐢 O(n) 栈空间 | ⚡ O(1) 固定空间 |
| 速度 | 🐢 较慢（CALL/RET 开销） | ⚡ 较快 |
| 可读性 | ✅ 数学定义直译 | 有时不够直观 |
| 适用范围 | 树、图、分治 | 线性问题 |
💡 编译器有时会自动把尾递归（tail recursion）优化成迭代——这种情况下递归既保留了可读性，又有迭代的性能。
尾递归（Tail Recursion）
尾递归是指递归调用是函数的最后一步操作，且返回值直接传递，不做额外计算：
// 非尾递归：返回后还要乘以 n
int fact(int n) {
if (n <= 1) return 1;
return n * fact(n - 1); // ← 还要做乘法，不是尾递归
}
// 尾递归：用累加器
int fact_tail(int n, int acc) {
if (n <= 1) return acc;
return fact_tail(n - 1, n * acc); // ← 直接返回，没有额外操作
}
为什么尾递归可以优化？
在尾递归中，当前栈帧在递归调用之后不再需要了——没有额外的计算，不需要返回后继续执行。所以编译器可以：
- 不创建新栈帧——直接在当前帧中更新参数
- 跳转到函数开头——而不是 CALL
- 效果 = 迭代，写法 = 递归
; 尾递归优化后的汇编（编译器生成）
; 不再有嵌套的 CALL，变成了循环！
_fact_tail:
; 参数：R0 = n, R1 = acc
loop:
CMP R0, #1 ; n <= 1 ?
JLE done ; 是 → 返回 acc
MUL R1, R0 ; acc = n * acc
SUB R0, #1 ; n = n - 1
JMP loop ; ← 直接跳回，不是 CALL！
done:
MOV R0, R1 ; 返回值 = acc
RET
⚡ 尾递归优化（TCO，Tail Call Optimization） 让递归的代码具有迭代的性能。写递归时尽量写成尾递归的形式——好编译器会帮你优化它。
有尾递归和没尾递归的区别
非尾递归 fact(5) 的栈： 尾递归 fact_tail(5, 1) 的栈：
┌──────────┐ （深度 5） ┌──────────┐ （深度 1）
│ n=5 │ │ n=5, acc │
│ ret→main │ │ → main │
├──────────┤ ├──────────┤
│ n=4 │ │ 只复用这一层 │
│ ret→fact │ │ │
├──────────┤ └──────────┘
│ n=3 │
│ ... │ ← 5 层栈帧
└──────────┘
另一个经典递归：斐波那契数列
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
汇编实现：
_fib:
; 序言
PUSH BP
MOV BP, SP
; [BP + 8] = n
LOAD R0, [BP + 8] ; R0 = n
CMP R0, #1 ; n <= 1 ?
JLE _fib_base ; 是 → 返回 n
; fib(n - 1)
LOAD R0, [BP + 8]
SUB R0, #1 ; R0 = n - 1
PUSH R0
CALL _fib
ADD SP, #4 ; 清理参数
; 此时 R0 = fib(n - 1)
; ⚠️ 马上要调用 fib(n - 2)，R0 会被覆盖！
PUSH R0 ; 保存 fib(n - 1) 到栈上
; fib(n - 2)
LOAD R0, [BP + 8]
SUB R0, #2 ; R0 = n - 2
PUSH R0
CALL _fib
ADD SP, #4 ; 清理参数
; 此时 R0 = fib(n - 2)
POP R1 ; R1 = fib(n - 1)（之前保存的）
ADD R0, R1 ; R0 = fib(n - 1) + fib(n - 2)
JMP _fib_end
_fib_base:
LOAD R0, [BP + 8] ; 返回 n 本身
_fib_end:
POP BP
RET
⚠️ fib 的效率问题：
fib(40)的递归调用次数是天文数字（约 3.3 亿次）。这是因为没有记忆化——fib(3)被重复计算了无数次。这就是为什么纯递归的 fib 在实践中基本不用，需要用动态规划或记忆化来优化。
fib(5) 的调用树：
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) ... ... ...
/ \
... ...
可以看到 fib(3) 被重复计算了 2 次，fib(2) 被重复计算了 3 次！
这个递归的时间复杂度是 O(2ⁿ)，n=100 时宇宙毁灭都算不完。
递归的常见错误
错误 1：缺少基本情况（无限递归）
_fact_bad:
PUSH BP
MOV BP, SP
LOAD R0, [BP + 8]
; ❌ 没有基本情况检查！
SUB R0, #1
PUSH R0
CALL _fact_bad ; 永远递归下去，直到栈溢出
ADD SP, #4
; ...
效果：程序运行时，栈不断增长，最终超出内存限制——栈溢出（Stack Overflow）。
错误 2：栈溢出（Stack Overflow）
递归深度太深时，栈会耗尽：
; 计算 fact(10000) → 递归深度 10000 层
; 每层栈帧至少 8-16 字节
; 总栈空间 ≈ 10000 × 16 = 160 KB
; 如果不巧栈上限只有 128 KB……
错误 3：寄存器冲突（最常见！）
_fib_bug:
; ...
PUSH R0 ; 保存 n？不，这是 R0，调用者保存的
CALL _fib
; R0 现在存了返回值
POP R1 ; 想恢复之前的值？ ❌ 栈顶现在是别的！
; ...
正确做法：在递归调用之前把需要保留的值 PUSH 到栈上，调用完成后 POP 回来。
错误 4：尾递归但调用者忘了传累加器
// 这是尾递归的正确调用方式：
// 调用者需要提供初始的累加器值
int result = fact_tail(5, 1); // ✅ acc 从 1 开始
// 如果调用者不传或传错：
int result = fact_tail(5, 0); // ❌ 0 × 任何数 = 0，永远返回 0！
观察：编译器生成的递归代码
写一段 C 代码，看看编译器会生成什么样的汇编：
int fact(int n) {
if (n <= 1) return 1;
return n * fact(n - 1);
}
编译器优化级别 -O0（无优化）生成的代码会和你手写的非常像——完整的序言/尾声，标准的栈帧操作。但加上 -O2（优化）后，编译器可能：
- 检测到这是尾递归 → 转换为迭代
- 或者直接内联展开小规模的递归 → 完全没有 CALL 指令
; -O0 版本（手写风格）： ; -O2 版本（优化后）：
_fact: _fact:
PUSH BP MOV R1, #1
MOV BP, SP loop:
LOAD R0, [BP + 8] CMP R0, #1
CMP R0, #1 JLE done
JLE base MUL R1, R0
; ...递归调用... SUB R0, #1
base: JMP loop
MOV R0, #1 done:
POP BP MOV R0, R1
RET RET
💡 这就是为什么现代 C 程序员可以写递归而不用担心性能——只要编译器足够聪明，递归代码在优化后和执行迭代几乎一样快（前提是尾递归）。
小结
递归和栈是一枚硬币的两面——没有栈机制，递归就不可能实现：
| 概念 | 要点 |
|---|---|
| 递归的本质 | 函数调用自身，每层调用有独立的栈帧 |
| 基本情况 | 必须有一个终止条件，否则无限递归 |
| 栈的使用 | 每层递归 = 一层新栈帧，返回时逐层弹出 |
| 栈溢出 | 递归太深或没有基本情况 |
| 尾递归 | 递归调用是最后一步，可被优化为迭代 |
| 性能考量 | 非尾递归通常比迭代慢，但代码更接近数学定义 |
递归 vs 迭代的取舍：
- 递归写起来更接近问题的数学定义（尤其是树、图、分治算法）
- 迭代通常更快、更省内存
- 尾递归 + 好编译器 = 两者兼得
为什么这很重要？ 递归是许多高级算法的基础——树的遍历、快速排序、图的深度优先搜索、回溯算法……理解递归在底层的栈实现，让你既能在高级语言中自如地写递归，又能理解什么时候该换成迭代来避免栈溢出。
接下来，你将进入汇编语言的进阶应用——如何把汇编和 C 语言混合编程，发挥两种语言各自的优势（此内容将在后续章节详细讲解）。