MIPS实现汉诺塔递归解决方案的寄存器保存恢复问题求助

Hey there! Let's break down what's going wrong with your MIPS Tower of Hanoi implementation and fix it step by step. The core issues are around how you're managing the stack and preserving registers during recursion—super common for beginners, so don't worry!

关键问题分析 #

• 缺失参数保存：当你为第一次递归调用修改$a0-$a3时，没有把这些参数的原始值保存到栈中。这意味着递归返回后，你会丢失执行print和第二次递归所需的原始n、from_rod等参数值。
• base_case中多余的栈操作：你在base_case里重复保存和恢复$ra，但进入hanoi函数时已经保存过$ra了，这会导致栈错位。
• print函数功能不全：当前的print只输出了杆的字符，没有还原C代码里完整的提示信息（比如"Move disk X from rod Y to rod Z"）。
• 栈空间不足：每次hanoi调用需要保存的不止是$ra，还需要保存原始参数，否则后续操作会丢失数据。

修正后的MIPS代码 #

.globl main

main:
    # 读取盘子数量（也可以像C代码一样硬编码li $a0,4）
    li $v0, 5
    syscall
    move $a0, $v0       # $a0 存储盘子数量n
    li $a1, 'A'         # $a1 存储起始杆from_rod
    li $a2, 'C'         # $a2 存储目标杆to_rod
    li $a3, 'B'         # $a3 存储辅助杆aux_rod

    jal hanoi

    # 退出程序
    li $v0, 10
    syscall

hanoi:
    # 栈帧分配：需要保存$ra、$a0-$a3（共5个寄存器，每个4字节，总计20字节）
    addi $sp, $sp, -20
    sw $ra, 16($sp)     # 保存返回地址到栈帧顶部
    sw $a0, 12($sp)     # 保存原始n值
    sw $a1, 8($sp)      # 保存原始起始杆
    sw $a2, 4($sp)      # 保存原始目标杆
    sw $a3, 0($sp)      # 保存原始辅助杆

    beq $a0, 1, base_case  # 基准情况：只有1个盘子时跳转

    # 第一次递归调用：hanoi(n-1, from, aux, to)
    addi $a0, $a0, -1   # n = n-1
    # 交换目标杆和辅助杆（$a2和$a3）
    move $t0, $a2
    move $a2, $a3
    move $a3, $t0
    jal hanoi

    # 恢复原始参数，用于打印和第二次递归
    lw $a0, 12($sp)
    lw $a1, 8($sp)
    lw $a2, 4($sp)
    lw $a3, 0($sp)

    # 打印当前盘子的移动步骤
    jal print

    # 第二次递归调用：hanoi(n-1, aux, to, from)
    addi $a0, $a0, -1   # n = n-1
    # 交换起始杆和辅助杆（$a1和$a3）
    move $t0, $a1
    move $a1, $a3
    move $a3, $t0
    jal hanoi

    # 清理栈并返回
    lw $ra, 16($sp)
    addi $sp, $sp, 20
    jr $ra

base_case:
    # 恢复原始参数，传递给print函数
    lw $a0, 12($sp)
    lw $a1, 8($sp)
    lw $a2, 4($sp)
    lw $a3, 0($sp)

    jal print

    # 清理栈并返回
    lw $ra, 16($sp)
    addi $sp, $sp, 20
    jr $ra

print:
    # 保存$ra和$a0（因为系统调用会修改$a0）
    addi $sp, $sp, -8
    sw $ra, 4($sp)
    sw $a0, 0($sp)

    # 打印"Move disk "
    li $v0, 4
    la $a0, move_msg
    syscall

    # 打印盘子编号（n）
    li $v0, 1
    lw $a0, 0($sp)
    syscall

    # 打印" from rod "
    li $v0, 4
    la $a0, from_msg
    syscall

    # 打印起始杆
    li $v0, 11
    move $a0, $a1
    syscall

    # 打印" to rod "
    li $v0, 4
    la $a0, to_msg
    syscall

    # 打印目标杆
    move $a0, $a2
    syscall

    # 打印换行
    li $a0, '\n'
    syscall

    # 恢复寄存器并返回
    lw $a0, 0($sp)
    lw $ra, 4($sp)
    addi $sp, $sp, 8
    jr $ra

# 字符串数据段
.data
move_msg: .asciiz "\n Move disk "
from_msg: .asciiz " from rod "
to_msg:   .asciiz " to rod "

核心要点解释 #

1. hanoi函数的栈帧设置：
   我们给栈分配了20字节空间，用来保存$ra和所有$a系列参数寄存器。这样即使递归调用修改了$a0-$a3，后续也能从栈中恢复原始值。

2. 参数恢复逻辑：
   第一次递归返回后，我们从栈中重新加载原始的n、杆编号等参数，确保打印的步骤和第二次递归调用的参数都是正确的。

3. 基准情况简化：
   基准情况不再做多余的$ra栈操作，只需要恢复参数、调用print，然后清理栈返回即可。

4. 完整的print函数：
   在.data段添加了对应字符串，用syscall 4（打印字符串）和syscall 1（打印整数）还原了C代码里的完整输出格式。

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