RISC-V递归函数实现调试求助：T(n)=4T(n/2)+2n+7执行报错

错误原因分析 #

这个错误的核心是程序尝试执行0地址处的内容，而0地址通常不属于指令区域。在递归场景下，绝大多数情况是返回寄存器（ra）未正确保存/恢复，或者栈帧管理失效导致递归返回时跳转到非法地址。

关键排查点 #

• 递归调用前必须保存ra寄存器到栈：RISC-V的jal指令会覆盖ra，如果不保存，递归返回时会丢失上层函数的返回地址，最终跳转到0地址。
• 检查递归终止条件的跳转逻辑：当n=1时，必须直接返回5，不能继续触发递归调用，否则会进入非法分支。
• 确保栈指针（sp）初始化合法：主函数启动时要将sp指向一块足够大的合法内存区域，避免栈溢出覆盖指令或数据。
• 验证参数计算的正确性：n/2需要用srai（算术右移）指令实现，确保整数除法的正确性，避免传递非法参数导致异常。

修正后的示例代码 #

# 递归函数T(n) = 4*T(n/2) + 2n +7，T(1)=5
# 调用约定：a0 = n，返回值存a0
T:
    # 栈帧：保存ra, s0（s0用来存当前n的值）
    addi    sp, sp, -16
    sw      ra, 12(sp)
    sw      s0, 8(sp)
    
    mv      s0, a0           # 保存当前n到s0
    li      t0, 1
    beq     s0, t0, base_case # 若n=1，跳转到基准情况
    
    # 计算T(n/2)：n/2 = s0 >> 1
    srai    a0, s0, 1
    jal     ra, T            # 递归调用T(n/2)，返回值在a0
    
    # 计算4*T(n/2)
    slli    a0, a0, 2        # a0 = 4*a0
    
    # 计算2n：s0是原n，2n = s0 <<1
    slli    t1, s0, 1
    add     a0, a0, t1       # a0 = 4T(n/2)+2n
    
    addi    a0, a0, 7        # 加上7，得到最终结果
    j       exit             # 跳转到恢复栈帧
    
base_case:
    li      a0, 5            # T(1)=5
    
exit:
    # 恢复栈帧和ra
    lw      s0, 8(sp)
    lw      ra, 12(sp)
    addi    sp, sp, 16
    ret                     # 返回ra指向的地址

# 主函数示例
main:
    # 初始化栈指针（假设栈从0x80001000开始，大小足够）
    li      sp, 0x80001000
    
    li      a0, 8            # 计算T(8)
    jal     ra, T
    
    # 这里可以添加打印结果的逻辑，比如调用ecall
    
exit_main:
    li      a7, 10           # 退出程序
    ecall

代码说明 #

• 递归函数T在调用jal前，先将ra和s0（保存当前n）压入栈，返回时恢复，确保上层函数的返回地址不丢失。
• 基准情况n=1直接返回5，避免无限递归。
• 主函数首先初始化栈指针到合法内存区域，这是很多初学者容易忽略的步骤——如果sp未初始化，栈操作会覆盖非法区域，导致返回地址被破坏。

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