如何在QtSpim/MIPS中实现带嵌套过程链接的递归序列a(n)=a(n-1)+2a(n-2)

我需要在MIPS/QtSpim中实现递归序列：

a(n) = a(n-1) + 2a(n-2)
初始条件为a(0) = a(1) = 1，程序要求提示用户输入n并输出结果，必须采用带嵌套过程链接的递归实现。但我写的代码在n>2时出错，原代码如下：

.data
a0: .word 1
a1: .word 1
n: .word 0
an: .word 0

.text
globl main

main:
    # Prompt user to enter the value of n
    li $v0, 4
    la $a0, prompt
    syscall

    # Read the value of n from the user
    li $v0, 5
    syscall
    move $s0, $v0

    # Call the sequence function
    move $a0, $s0
    jal sequence

    # Display the result
    li $v0, 1
    lw $a0, an
    syscall

    # Exit program
    li $v0, 10
    syscall

sequence:
    addi $sp, $sp, -4
    sw $ra, 0($sp)
    beq $a0, 0, a0_case
    beq $a0, 1, a1_case
    addi $a0, $a0, -1
    jal sequence
    lw $t0, an
    addi $a0, $a0, -1
    jal sequence
    lw $t1, an
    add $v0, $t0, $t1
    sll $t1, $t1, 1
    add $t0, $t0, $t1
    sw $t0, an
    j end

a0_case:
    li $v0, 1
    sw $v0, an
    j end

a1_case:
    li $v0, 1
    sw $v0, an

end:
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

.data
prompt: .asciiz "Enter the value of n: "

.text

问题根源 #

1. 段定义混乱：原代码重复定义.data和.text段，导致QtSpim无法正确解析程序结构，是n>2时出错的核心原因之一。
2. 全局变量冲突：用全局变量an存储递归中间结果，嵌套调用时后续计算会覆盖该变量值，导致前面的中间结果丢失，计算逻辑失效。
3. 冗余计算逻辑：代码中add $v0, $t0, $t1属于冗余操作，后续的移位和加法才是正确计算，但逻辑混乱容易引发错误。

修复后的代码 #

.data
prompt: .asciiz "Enter the value of n: "

.text
.globl main

main:
    # 提示用户输入n
    li $v0, 4
    la $a0, prompt
    syscall

    # 读取输入的n值
    li $v0, 5
    syscall
    move $a0, $v0

    # 调用递归函数
    jal sequence

    # 输出计算结果
    li $v0, 1
    move $a0, $v0
    syscall

    # 退出程序
    li $v0, 10
    syscall

sequence:
    # 保存返回地址到栈
    addi $sp, $sp, -4
    sw $ra, 0($sp)

    # 基线条件：n=0或n=1时返回1
    beq $a0, 0, return_one
    beq $a0, 1, return_one

    # 计算a(n-1)：保存当前n值到栈，避免调用后丢失
    addi $sp, $sp, -4
    sw $a0, 0($sp)
    addi $a0, $a0, -1
    jal sequence
    move $t0, $v0

    # 计算a(n-2)：恢复保存的n值，再减2
    lw $a0, 0($sp)
    addi $sp, $sp, 4
    addi $a0, $a0, -2
    jal sequence
    move $t1, $v0

    # 计算a(n) = a(n-1) + 2*a(n-2)
    sll $t1, $t1, 1
    add $v0, $t0, $t1

    # 恢复返回地址并返回
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

return_one:
    li $v0, 1
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

修复说明 #

1. 规范段结构：将所有数据放在.data段、代码放在.text段，避免重复定义导致的解析错误。
2. 移除全局变量：遵循MIPS函数调用约定，用$v0寄存器返回递归结果，彻底解决全局变量的竞争问题。
3. 栈保存关键值：递归调用前将当前$a0（n值）保存到栈中，确保计算n-2时能获取正确初始值。
4. 简化基线条件：合并n=0和n=1的分支，简化代码结构。
5. 明确计算逻辑：通过左移操作实现乘2，再与a(n-1)相加，保证计算结果符合递归公式。

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