求助：解析MIPS中基于栈的递归函数调用（以阶乘为例）

栈是CPU管理函数调用上下文的核心结构，递归能层层调用自身再逐层返回，全靠栈保存每一次调用的独立状态。下面结合C语言阶乘函数及其MIPS汇编实现，拆解整个过程。

先看C语言阶乘递归代码 #

int fact(int n) {
    if (n == 0) {
        return 1; // 基线条件：递归终止点
    }
    return n * fact(n-1); // 递归调用自身
}

当调用fact(3)时，会依次触发fact(3)→fact(2)→fact(1)→fact(0)，直到触发基线条件后开始逐层返回计算结果。栈的操作就发生在每一次调用和返回的节点上。

MIPS汇编对应的实现与栈操作详解 #

下面是对应阶乘函数的简化MIPS汇编，重点看栈的压入（存储）和弹出（回载）逻辑：

fact:
    # 1. 栈帧初始化：分配空间并保存上下文
    addi    $sp, $sp, -8       # 栈指针减8，给当前调用分配8字节栈空间
    sw      $ra, 4($sp)        # 把返回地址$ra存入栈的4字节位置（避免递归调用覆盖）
    sw      $a0, 0($sp)        # 把当前参数n存入栈的0字节位置（后续递归会修改$a0）

    # 2. 基线条件判断
    beq     $a0, $zero, base_case  # 如果n=0，直接跳转到基线处理逻辑

    # 3. 发起递归调用
    addi    $a0, $a0, -1       # 参数n减1，准备调用fact(n-1)
    jal     fact               # 调用fact，此时CPU会自动把当前指令的下一条地址存入$ra

    # 4. 递归返回后的计算：n * fact(n-1)
    lw      $a0, 0($sp)        # 从栈中恢复当前层的原始n值
    mul     $v0, $a0, $v0      # 用原始n乘以下一层递归的返回值（存在$v0中）

exit:
    # 5. 栈帧回载：恢复上下文并释放空间
    lw      $ra, 4($sp)        # 从栈中取出之前保存的返回地址$ra
    addi    $sp, $sp, 8        # 栈指针加8，释放当前层的栈空间
    jr      $ra                # 跳回上一层调用的位置

base_case:
    li      $v0, 1             # 基线条件返回1，存在返回值寄存器$v0中
    j       exit               # 跳转到exit流程，恢复栈并返回

栈的存储（压栈）过程（以fact(3)为例） #

1. 调用fact(3)：
   • 栈指针$sp减8，分配栈空间；
   • 把主函数的返回地址存入栈的4字节位置，把参数3存入栈的0字节位置；
   • 判断3≠0，参数减1变为2，调用fact(2)。
2. 调用fact(2)：
   • 重复栈帧初始化操作，保存当前返回地址和参数2到新的栈空间；
   • 参数减1变为1，调用fact(1)。
3. 调用fact(1)：
   • 保存返回地址和参数1到栈；
   • 参数减1变为0，调用fact(0)。
4. 调用fact(0)：
   • 保存返回地址和参数0到栈；
   • 触发基线条件，直接设置返回值1，进入回载流程。

此时栈从栈顶到栈底的存储内容（简化）：[返回地址4, 0] → [返回地址3, 1] → [返回地址2, 2] → [返回地址1, 3]

栈的回载（弹栈）过程 #

1. fact(0)返回：
   • 从栈中取出保存的返回地址，栈指针加8释放空间；
   • 跳回fact(1)中jal fact的下一条指令，此时$v0的值是1。
2. fact(1)计算并返回：
   • 从栈中恢复原始参数1，执行1*1=1，把结果存入$v0；
   • 恢复返回地址，释放栈空间，跳回fact(2)的后续指令。
3. fact(2)计算并返回：
   • 恢复参数2，执行2*1=2存入$v0；
   • 恢复返回地址，释放栈空间，跳回fact(3)的后续指令。
4. fact(3)计算并返回：
   • 恢复参数3，执行3*2=6存入$v0；
   • 恢复主函数的返回地址，释放栈空间，跳回主函数，完成整个递归流程。

核心总结 #

• 存储（压栈）：每一次递归调用时，函数都会把当前调用的关键上下文（返回地址、参数、需要保留的寄存器）压入栈中，为下一层递归调用腾出寄存器资源，同时保证当前层的状态不会被覆盖。
• 回载（弹栈）：当递归到达基线条件开始返回时，函数会从栈中逐层取出之前保存的上下文，恢复寄存器和参数，计算当前层的结果后返回上一层，直到所有栈帧被释放，回到初始调用点。

内容的提问来源于stack exchange，提问作者Ahmad Fardous Azimi