RISC-V递归斐波那契汇编代码问题：n>2计算错误

问题场景 #

编写的RISC-V递归斐波那契汇编代码，仅能正确计算数字1和2的结果，当输入大于2的数字时，计算结果错误，还出现寄存器写入异常。原代码如下：

.text
.globl _start
.globl fib       # Export function 'fib'

# Entry point
_start:
    addi a0, x0, 4       # Load 4 into a0
    jal ra, fib          # Jump to fib

fib:
    # Check base cases
    addi t0, x0, 1              # Load 1 into t0
    beq a0, t0, base_case       # If n == 1, jump to base_case
    addi t0, x0, 2              # Load 2 into t0
    beq a0, t0, base_case       # If n == 2, jump to base_case

    # Recursive call for F(n-1)
    addi sp, sp, -4             # Allocate stack space for return address
    sw ra, 0(sp)                # Save return address on the stack
    addi sp, sp, -4             # Allocate stack space for intermediate results
    sw a0, 0(sp)                # Save current value of a0 (n)
    addi a0, a0, -1             # a0 = a0 - 1 (n-1)
    jal ra, fib                 # Call fib(n-1)
    lw t1, 0(sp)                # Load result of F(n-1) into t1
    addi sp, sp, 4              # Restore stack pointer
    lw ra, 0(sp)                # Load return address from the stack
    addi sp, sp, 4              # Restore stack pointer

    # Recursive call for F(n-2)
    addi sp, sp, -4             # Allocate stack space for return address
    sw ra, 0(sp)                # Save return address on the stack
    addi sp, sp, -4             # Allocate stack space for intermediate results
    sw t1, 0(sp)                # Save F(n-1) on the stack
    addi a0, a0, -1             # a0 = a0 - 1 (n-2)
    jal ra, fib                 # Call fib(n-2)
    lw t1, 0(sp)                # Load F(n-1) from the stack into t1
    addi sp, sp, 4              # Restore stack pointer
    lw ra, 0(sp)                # Load return address from the stack
    addi sp, sp, 4              # Restore stack pointer

    # Add results
    add a0, t1, a0              # a0 = t1 + a0 (F(n-1) + F(n-2))
    jalr x0, ra, 0              # Return to the calling function

base_case:
    addi a0, x0, 1              # Base case: result = 1
    jalr x0, ra, 0              # Return to the calling function

问题根源分析 #

1. 栈操作逻辑错误：计算F(n-1)时，调用fib返回的结果存在a0中，但代码错误地从栈中读取原输入的n值存入t1，完全混淆了输入值和计算结果。
2. F(n-2)的参数错误：调用完F(n-1)后，a0是F(n-1)的结果，此时直接执行addi a0, a0, -1得到的不是n-2，而是F(n-1)-1，参数传递完全错误。
3. 冗余且混乱的栈管理：多次重复分配栈空间保存ra，栈的分配和释放没有统一规划，容易导致栈指针错位，破坏栈中存储的数据。

修复后的代码 #

.text
.globl _start
.globl fib       # Export function 'fib'

# Entry point
_start:
    addi a0, x0, 4       # Load 4 into a0
    jal ra, fib          # Jump to fib
loop:                    # 程序终止逻辑，防止计算完成后跑飞
    j loop

fib:
    # 检查基例
    addi t0, x0, 1              # 加载1到t0
    beq a0, t0, base_case       # 若n==1，跳转到基例
    addi t0, x0, 2              # 加载2到t0
    beq a0, t0, base_case       # 若n==2，跳转到基例

    # 一次性分配栈空间，保存返回地址ra和当前n值
    addi sp, sp, -8
    sw ra, 4(sp)                # 保存ra到栈的高4字节
    sw a0, 0(sp)                # 保存当前n值到栈的低4字节

    # 递归计算F(n-1)
    addi a0, a0, -1             # 设置参数为n-1
    jal ra, fib                 # 调用fib(n-1)，结果存入a0
    add t1, a0, x0              # 将F(n-1)的结果暂存到t1

    # 递归计算F(n-2)
    lw a0, 0(sp)                # 从栈中恢复原n值
    addi a0, a0, -2             # 设置参数为n-2
    jal ra, fib                 # 调用fib(n-2)，结果存入a0

    # 计算最终结果：F(n) = F(n-1) + F(n-2)
    add a0, t1, a0

    # 恢复栈和返回地址
    lw ra, 4(sp)
    addi sp, sp, 8
    jalr x0, ra, 0              # 返回调用方

base_case:
    addi a0, x0, 1              # 基例返回1
    jalr x0, ra, 0              # 返回调用方

修复说明 #

• 修正数据读取逻辑：调用fib(n-1)后，直接将a0中的结果存入t1，不再错误读取栈中的原n值；计算fib(n-2)时，从栈中恢复原n值再减2，保证参数正确。
• 优化栈管理：进入递归分支后一次性分配8字节栈空间，同时保存ra和原n值，退出时一次性恢复栈，确保栈平衡，避免指针错位。
• 减少冗余操作：仅在进入递归分支时保存一次ra，后续递归调用不会破坏外层的返回地址，避免重复保存的冗余操作。
• 添加终止逻辑：在_start中调用fib后添加无限循环，防止计算完成后程序无意义地继续执行导致异常。

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