使用栈帧递归计算斐波那契数列返回值始终为1的问题排查

你的代码里有几个核心逻辑错误，导致返回值始终为1，逐一拆解如下：

1. 栈帧初始化彻底混乱 #

在fib函数开头，你依次压入$ra、$fp、$s0、$s1后，执行addiu $fp, $sp, -8和move $sp, $fp——这一步直接把栈指针$sp覆盖成了$fp的新值，之前压入栈的所有寄存器数据全部丢失，后续栈操作完全错位。

修正方案：
正确的栈帧初始化应该先保存寄存器，再设置帧指针：

fib:
    addiu   $sp, $sp, -16       # 为4个寄存器分配16字节栈空间
    sw      $ra, 12($sp)        # 按顺序保存ra、fp、s0、s1
    sw      $fp, 8($sp)
    sw      $s0, 4($sp)
    sw      $s1, 0($sp)
    addiu   $fp, $sp, 12        # 帧指针指向ra的存储位置，方便访问参数

2. 参数读取偏移量完全错误 #

你用lw $t3, 24($fp)获取传入的n，但由于栈帧初始化错误，这个偏移量毫无意义。在正确的栈帧结构下，调用者传入的参数位于$fp + 4的位置，所以正确的参数读取应该是：

lw  $t3, 4($fp)                # 从帧指针上方4字节处读取参数n

3. 递归参数传递逻辑错误 #

计算fib(n-2)时，你写了addi $s0, $s0, -2——但此时$s0已经被赋值为fib(n-1)的返回值，不是原始的n了，导致第二次递归调用的参数完全错误。同时，你把fib(n-1)的结果存在$s0，覆盖了原始n，也无法正确计算n-2。

修正方案：
把原始n存在$s0，fib(n-1)的结果存在$s1，用原始n计算n-2：

move    $s0, $t3               # s0保存原始n
li      $v0, 1
ble     $s0, 1, epilog

# 计算fib(n-1)
addi    $a0, $s0, -1           # 用a0传递参数（符合MIPS调用约定）
jal     fib
move    $s1, $v0               # s1保存fib(n-1)的结果

# 计算fib(n-2)
addi    $a0, $s0, -2           # 用原始n计算n-2
jal     fib
add     $v0, $s1, $v0          # 累加两个递归结果

4. 栈帧恢复顺序错误 #

你的epilog部分恢复寄存器的顺序和压栈顺序不匹配，且栈指针偏移错误。正确的恢复应该遵循后进先出原则，最后压入的寄存器先恢复：

epilog:
    lw      $s1, 0($sp)         # 先恢复最后压入的s1
    lw      $s0, 4($sp)
    lw      $fp, 8($sp)
    lw      $ra, 12($sp)
    addiu   $sp, $sp, 16        # 释放栈空间
    jr      $ra

5. main函数传参优化（可选） #

你当前手动压栈传递参数，容易出错。按照MIPS调用约定，参数应该放在$a0中，main里的调用逻辑可以简化为：

# main中调用fib的部分替换为：
move    $a0, $v0               # 把输入的n放到a0寄存器
jal     fib
move    $t7, $v0               # 保存返回值

修正后的完整fib函数示例 #

fib:
    addiu   $sp, $sp, -16
    sw      $ra, 12($sp)
    sw      $fp, 8($sp)
    sw      $s0, 4($sp)
    sw      $s1, 0($sp)
    addiu   $fp, $sp, 12

    lw      $t3, 4($fp)
    move    $s0, $t3
    li      $v0, 1
    ble     $s0, 1, epilog

    addi    $a0, $s0, -1
    jal     fib
    move    $s1, $v0

    addi    $a0, $s0, -2
    jal     fib
    add     $v0, $s1, $v0

epilog:
    lw      $s1, 0($sp)
    lw      $s0, 4($sp)
    lw      $fp, 8($sp)
    lw      $ra, 12($sp)
    addiu   $sp, $sp, 16
    jr      $ra

内容的提问来源于stack exchange，提问作者oscamosca_