一个递归的底层实现

基于RISCV32I指令集的简单实例

C语言原始代码

int fact(int n){
	if(n<1) return 1;
	else return n*fact(n-1);
}

riscv汇编实现(ripes模拟器)

.data
n:.word 10
.text
.global main
main:
	lw x10,n
	jal x1,fact
	li a7,10
	ecall
fact:
	addi sp, sp, -8
	sw x1, 4(sp)
	sw x10, 0(sp)
	addi x5,x10,-1 # n-1
	bge x5,x0,L1
	addi x10,x0,1
	addi sp, sp, 8
	ret
L1:
	addi x10,x10,-1
	jal x1,fact
	addi x6,x10,0
	lw x10,0(sp)
	lw x1,4(sp)
	addi sp ,sp, 8
	mul x10,x10,x6
	ret

代码讲解

基础指令解析

1. 栈操作指令

   • addi sp, sp, -8：栈指针下移8字节（开辟栈帧）
   • sw x1, 4(sp)：将返回地址（ra）保存到栈顶+4的位置
   • lw x10, 0(sp)：从栈顶恢复调用者的n值

2. 控制流指令

   • bge x5, x0, L1：判断n-1是否≥0，决定是否继续递归
   • jal x1, fact：跳转并链接（保存返回地址到x1）

3. 运算指令

   • mul x10, x10, x6：关键乘法操作（递归结果与当前n相乘）
   • addi x10, x10, -1：实现n-1的参数传递

栈的使用（核心机制）

递归调用时栈的变化过程（以n=2为例）：

|---------------|  
|    main的ra    | <-- 初始栈顶  
|---------------|
        ↓ 第一次调用fact(2)
|---------------|
|   fact(2)的ra  |  ← sp+4  
|       n=2      |  ← sp      ← 分配8字节
|---------------|
        ↓ 调用fact(1)
|---------------|
|   fact(1)的ra  |  
|       n=1      |  
|---------------|
        ↓ 调用fact(0)
|---------------|
|   fact(0)的ra  |  
|       n=0      |  
|---------------|

当n=0时触发递归终止：

1. 返回1（x10=1）
2. 弹出栈帧（sp +=8）
3. 返回至fact(1)的调用点

寄存器的变化轨迹

栈视角fact(4)全过程

一、栈帧结构说明

• 每个 fact调用产生 8字节栈帧：

|---------------| 高地址
|   保存的RA(x1)  | ← sp+4 (旧栈顶方向)
|---------------|
|   当前n值(x10)  | ← sp (新栈顶)
|---------------| 低地址

二、递归展开阶段（压栈过程）

1. 初始调用 fact(4)

寄存器状态：
x10=4, x1=main返回地址(0x8)

执行指令：
addi sp,sp,-8  # sp下移8字节
sw x1,4(sp)     # 保存main的返回地址
sw x10,0(sp)    # 保存n=4

栈状态：

|---------------|
| main的RA(0x8)  | ← sp+4
|---------------|
|     n=4       | ← sp
|---------------| 

2. 调用 fact(3)

参数准备：
addi x10,x10,-1  # x10=3
jal x1,fact      # 保存RA=0x34到x1

新栈帧：
addi sp,sp,-8
sw x1,4(sp)      # 保存RA=0x34
sw x10,0(sp)     # 保存n=3

栈状态：

|---------------|
|  fact(4)RA(0x34)| ← sp+12
|---------------|
|     n=4        | ← sp+8
|---------------|
|  fact(3)RA(0x34)| ← sp+4
|---------------|
|     n=3        | ← sp
|---------------|

3. 递归到 fact(0)

持续递归直到n=0时：

|---------------|
|  fact(1)RA(0x34)| ← sp+4*(2n+1)
|---------------|
|     n=1        | 
|---------------|
|  fact(0)RA(0x34)| ← sp+4
|---------------|
|     n=0        | ← sp
|---------------|

三、递归收缩阶段（弹栈计算）

1. fact(0)返回1

执行分支：
addi x10,x0,1    # x10=1
addi sp,sp,8     # 弹出n=0的栈帧
ret              # 返回至fact(1)的0x34地址

栈状态回退：

|---------------|
|  fact(1)RA(0x34)| ← sp+4
|---------------|
|     n=1        | ← sp
|---------------|

2. fact(1)计算1*1=1

恢复现场：
lw x10,0(sp)     # x10=1 (原n=1)
lw x1,4(sp)      # 恢复RA=fact(2)调用点
addi sp,sp,8     # 弹出栈帧

执行计算：
mul x10,x10,x6   # 1*1=1 → x10=1

栈状态：

|---------------|
|  fact(2)RA(0x34)| ← sp+4
|---------------|
|     n=2        | ← sp
|---------------|

3. fact(2)计算2*1=2

恢复n=2后计算：
mul x10,x10,x6   # 2*1=2 → x10=2

栈继续回退，直到：

4. fact(4)最终计算4*6=24

最终栈帧：
|---------------|
| main的RA(0x8)  | ← sp+4
|---------------|
|     n=4       | ← sp
|---------------|

执行计算：
mul x10,x10,x6   # 4*6=24 → x10=24
ret              # 返回main函数

四、递归栈的核心特征

1. 后进先出：最后调用的fact(0)最先完成计算
2. 环境保存：每个栈帧独立保存：
   • 返回地址（保证能正确回溯）
   • 当前n值（用于后续乘法计算）
3. 空间代价：递归深度与栈空间消耗成正比（fact(n)需要n+1层栈帧，故数字过大爆栈

反汇编解析

00000014 <fact>:
14: ff810113  addi sp,sp,-8   # 开辟8字节栈空间
18: 00112223  sw ra,4(sp)     # 保存返回地址到栈
1c: 00a12023  sw a0,0(sp)     # 保存当前n值到栈
20: fff50293  addi t0,a0,-1    # 计算n-1
24: 0002d863  bge t0,zero,34 <L1> # 判断是否继续递归

# 递归终止分支
28: 00100513  addi a0,zero,1   # 设置返回值1
2c: 00810113  addi sp,sp,8     # 弹出栈帧
30: 00008067  ret              # 直接返回

00000034 <L1>:
34: fff50513  addi a0,a0,-1    # 准备n-1参数
38: fddff0ef  jal ra,-36 <fact> # 递归调用
3c: 00050313  mv t1,a0         # 保存递归结果到t1
40: 00012503  lw a0,0(sp)      # 恢复当前层n值
44: 00412083  lw ra,4(sp)      # 恢复返回地址
48: 00810113  addi sp,sp,8     # 弹出栈帧
4c: 02650533  mul a0,a0,t1     # 计算n*递归结果
50: 00008067  ret              # 返回