MIPS递归函数Myfun运行异常与结果错误问题求助

问题描述 #

• 输入2时触发运行时错误：line 31: Runtime exception at 0x00400038: address out of range 0x7fbffffc Go: execution terminated with errors.
• 输入3时输出3（预期结果为0）；输入4时输出4（预期结果为8）

预期实现的C语言逻辑 #

int Myfun (int N)
{
 if (N>3) return ( Myfun(N-2) + 2*N );
 else return 0;
}

编写的MIPS汇编代码 #

.data
input: .asciiz "Input: "
    .text
    .globl main
main:
    # Prompt user for input
    li $v0, 4
    la $a0, input
    syscall

    # Get user input
    li $v0, 5
    syscall
    move $a0, $v0

    # Call Myfun(N)
    jal Myfun

    # Print the result
    li $v0, 1
    syscall

    # Exit
    li $v0, 10
    syscall

Myfun:
    addi $sp, $sp, -8       # Reserve stack space for 2 items
    sw $ra, 4($sp)          # Save the return address
    sw $a0, 0($sp)          # Save the current value of N
    slti $t0, $a0, 3        # Test if N is less than 3
    beq $t0, $zero, Base_case     # If N < 3, jump to base_case
    addi $a0, $a0, -2       # Prepare the argument for the recursive 
    jal Myfun               # Recursive call
    lw $a0, 0($sp)          # After returning, load the original N
    add $t1, $a0, $a0     # Calculate 2N
    add $v0, $v0, $t1       # Add 2N to the result of the recursive 
    j Exit                  # Return from the function

Base_case:
    li $v0, 0         # Set the return value to 0 for the base case
    j Exit

Exit:
    lw $a0, 0($sp)
    lw $ra, 4($sp)          # Restore the return address
    addi $sp, $sp, 8        # Clean up the stack
    jr $ra                  # Return from the function

问题分析与修复 #

1. 分支判断逻辑完全颠倒 #

原代码用slti $t0, $a0, 3判断N是否小于3，然后beq $t0, $zero, Base_case的逻辑是：当N不小于3时跳转到Base_case，这和C语言要求的“N>3时递归，否则返回0”完全相反。

正确的判断应该是：

• 用sgt $t0, $a0, 3判断N是否大于3（N>3时$t0=1，否则为0）
• 当$t0为0时（即N<=3）跳转到Base_case，否则进入递归分支

2. 无限递归导致栈溢出 #

输入2时，原逻辑会错误进入递归分支：N=2时slti $t0, $a0,3得到$t0=1，beq $t0, $zero不成立，所以执行递归操作，把N减2变成0，继续调用Myfun(0)，之后又重复减2得到-2，无限递归下去耗尽栈空间，触发地址越界错误。

3. Exit段冗余恢复$a0 #

Exit段中的lw $a0, 0($sp)是多余的，MIPS调用约定中$a0-$a1属于临时寄存器，函数返回后不需要恢复其原值，冗余操作可能增加出错风险。

修正后的代码 #

.data
input: .asciiz "Input: "
    .text
    .globl main
main:
    # Prompt user for input
    li $v0, 4
    la $a0, input
    syscall

    # Get user input
    li $v0, 5
    syscall
    move $a0, $v0

    # Call Myfun(N)
    jal Myfun

    # Print the result
    li $v0, 1
    syscall

    # Exit
    li $v0, 10
    syscall

Myfun:
    addi $sp, $sp, -8       # 分配栈空间保存ra和a0
    sw $ra, 4($sp)          # 保存返回地址
    sw $a0, 0($sp)          # 保存当前N值
    
    sgt $t0, $a0, 3         # 判断N是否大于3
    beq $t0, $zero, Base_case  # N<=3时进入基例
    
    addi $a0, $a0, -2       # 准备递归参数N-2
    jal Myfun               # 递归调用Myfun(N-2)
    
    lw $a0, 0($sp)          # 恢复原N值
    add $t1, $a0, $a0       # 计算2*N
    add $v0, $v0, $t1       # 递归结果加上2*N
    j Exit

Base_case:
    li $v0, 0               # 基例返回0
    j Exit

Exit:
    lw $ra, 4($sp)          # 恢复返回地址
    addi $sp, $sp, 8        # 释放栈空间
    jr $ra                  # 返回调用者

验证结果 #

• 输入2：进入基例，返回0，无运行错误
• 输入3：进入基例，返回0，符合预期
• 输入4：递归调用Myfun(2)返回0，加上2*4=8，最终返回8，符合预期

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