MIPS递归实现杨辉三角问题：递归函数返回语句故障排查

嘿，我帮你排查下MIPS实现杨辉三角递归时遇到的运行中断问题！首先咱们先把你给出的C代码补全（方便对照逻辑），然后拆解MIPS递归中最容易踩坑的返回语句和栈帧维护问题。

参考C代码（完整版本） #

先把你的C代码补全，明确递归逻辑：

// C Language
#include <stdio.h>
int trianguloPascal(int i, int k);
int main(void) {
    int num, i, j, k;
    printf("Introduce el número de filas: ");
    scanf("%i", &num);
    for (i = 0; i < num; i++) {
        // 打印前置空格对齐
        for (j = num; j > i; j--) {
            printf(" ");
        }
        for (k = 0; k <= i; k++) {
            printf("%d ", trianguloPascal(i, k));
        }
        printf("\n");
    }
    return 0;
}

int trianguloPascal(int i, int k) {
    // 边界条件：首尾元素都是1
    if (k == 0 || k == i) {
        return 1;
    }
    // 递归公式：C(i,k) = C(i-1,k-1) + C(i-1,k)
    return trianguloPascal(i-1, k-1) + trianguloPascal(i-1, k);
}

MIPS递归的核心问题：返回语句与栈帧维护 #

你代码运行中断的大概率原因是没有正确维护栈帧和返回地址，MIPS递归中必须严格做好以下几点：

1. 递归前必须保存上下文到栈 #

每次进入递归函数，要把$ra（返回地址）和会被修改的s寄存器（因为s寄存器是保存寄存器，调用者期望它们的值不变）压入栈，否则递归调用会覆盖原来的返回地址，导致函数无法正确返回，直接触发中断。

2. 返回值必须存在$v0寄存器 #

MIPS约定函数返回值存在$v0，不管是边界条件返回1，还是递归相加的结果，都要把值放到$v0里。

3. 递归结束后必须恢复栈帧并正确返回 #

递归逻辑执行完后，要从栈中恢复之前保存的寄存器，然后用jr $ra回到调用者的位置，同时要释放栈空间，避免栈溢出。

修正后的MIPS完整代码 #

下面是按照上述规则实现的MIPS代码，重点标注了返回相关的逻辑：

.data
prompt: .asciiz "Introduce el número de filas: "
space: .asciiz " "
newline: .asciiz "\n"

.text
.globl main

main:
    # 打印提示信息
    li $v0, 4
    la $a0, prompt
    syscall

    # 读取输入的行数，存入$t0
    li $v0, 5
    syscall
    move $t0, $v0

    # 外层循环：i从0到num-1（$t1 = i）
    li $t1, 0
outer_loop:
    bge $t1, $t0, exit_main

    # 打印前置空格对齐
    move $t2, $t0
space_loop:
    ble $t2, $t1, end_space_loop
    li $v0, 4
    la $a0, space
    syscall
    addi $t2, $t2, -1
    j space_loop
end_space_loop:

    # 内层循环：k从0到i（$t3 = k）
    li $t3, 0
inner_loop:
    bgt $t3, $t1, end_inner_loop

    # 调用递归函数：参数$a0=i, $a1=k
    move $a0, $t1
    move $a1, $t3
    jal trianguloPascal

    # 打印当前杨辉三角元素
    move $a0, $v0
    li $v0, 1
    syscall
    li $v0, 4
    la $a0, space
    syscall

    addi $t3, $t3, 1
    j inner_loop
end_inner_loop:

    # 换行
    li $v0, 4
    la $a0, newline
    syscall

    addi $t1, $t1, 1
    j outer_loop

exit_main:
    # 退出程序
    li $v0, 10
    syscall

# 递归函数：trianguloPascal(i, k)，返回值存于$v0
trianguloPascal:
    # 分配栈空间：保存$ra、$s0、$s1（每个4字节，共12字节）
    addi $sp, $sp, -12
    sw $ra, 8($sp)   # 保存返回地址到栈
    sw $s0, 4($sp)   # 保存$a0（i）到$s0
    sw $s1, 0($sp)   # 保存$a1（k）到$s1

    # 把参数存入$s寄存器，方便递归调用时使用
    move $s0, $a0
    move $s1, $a1

    # 边界条件：k=0或k=i，返回1
    beq $s1, $zero, return_one
    beq $s1, $s0, return_one

    # 第一次递归调用：trianguloPascal(i-1, k-1)
    addi $a0, $s0, -1
    addi $a1, $s1, -1
    jal trianguloPascal
    move $t4, $v0  # 暂存第一个递归结果

    # 第二次递归调用：trianguloPascal(i-1, k)
    addi $a0, $s0, -1
    move $a1, $s1
    jal trianguloPascal
    add $v0, $t4, $v0  # 两个结果相加，作为返回值

    # 跳转到恢复栈帧的部分
    j end_recursion

return_one:
    li $v0, 1  # 边界条件返回1，存入$v0

end_recursion:
    # 从栈中恢复寄存器
    lw $s1, 0($sp)
    lw $s0, 4($sp)
    lw $ra, 8($sp)
    addi $sp, $sp, 12  # 释放栈空间

    jr $ra  # 回到调用者的位置，完成返回

关键细节解释 #

• 栈帧维护：在trianguloPascal函数开头，我们给栈分配了12字节空间，用来保存$ra、$s0、$s1，这样递归调用时不会覆盖这些关键值。
• 返回逻辑：边界条件直接给$v0赋值1；递归相加后把结果存入$v0，最后通过jr $ra返回，这是MIPS函数返回的标准方式，不能用其他跳转指令替代，否则会导致程序地址错误。
• 寄存器使用：$s寄存器是保存寄存器，调用者期望它们的值在函数调用后不变，所以必须保存到栈里，递归结束后恢复。

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