MIPS汇编实现卡特兰数递归算法出错，请求问题定位与修正

测试用例 #

Program input:
0 1 2 3 6 9 
Expected output:
1 1 2 5 132 4862 
Obtained output:
1 1 2 4 32 256   

可见当n=3时，预期输出为5，实际输出为4，后续结果全部错误，问题出在循环计算部分，以下是错误代码及修正方案：

错误的MIPS汇编代码 #

catalan_recur:
addi $sp,$sp,-12
sw $ra,0($sp)
sw $s0,4($sp)
sw $a0,8($sp)
addi $t0,$0,1

bgt $a0,$t0,catalan_recur_else     #a0>1 ?
li $v0, 1
lw $s0, 4($sp)
lw $ra, 0($sp)
addiu $sp, $sp, 12
jr $ra

catalan_recur_else:
  li $t1,0         #res=0
  li $t2,0         #i=0
catalan_recur_loop:  
  bge $t2, $a0, end_loop  # if i >= n, exit loop
   # res += catalan_recur(i)*catalan_recur(n-i-1)
  move $a0, $t2              
  jal catalan_recur          # call catalan_recur(i)        
  add $s0,$0,$v0             # get return value and store in $s0
  lw $a0,8($sp)
  addi $t2,$t2,1             # i++
  sub $a0,$a0,$t2            # calculate n-i-1
  jal catalan_recur          # call catalan_recur(n-i-1)
  mult $s0,$s0,$v0           # catalan_recur(i) * catalan_recur(n-i-1)
  add $t1,$t1,$s0            # add to res
  lw $s0,4($sp)
  lw $a0,8($sp)
  j catalan_recur_loop  
        
end_loop:
  move $v0, $t1               # move res to $v0
  lw $a0,8($sp)
  lw $s0,4($sp)        
  lw $ra, 0($sp)
  addiu $sp, $sp, 12
jr $ra

对应伪代码 #

def catalan_recur(n):
    if n <= 1:
        return 1;
    else:
        res = 0
        for i in range(n):  # i = 0 ~ (n-1)
            res += catalan_recur(i) * catalan_recur(n-i-1)
         return res;

# a0: 输入的正整数参数n

错误分析与修正 #

1. 乘法指令使用错误 #

MIPS的mult指令仅接受两个寄存器操作数，且乘法结果存入hi和lo寄存器，原代码中mult $s0,$s0,$v0是非法语法，正确做法是用mult $s0, $v0，之后通过mflo取出低32位结果存入临时寄存器。

2. 循环中i的递增时机错误 #

原代码在调用catalan_recur(i)后立即执行i++，导致计算n-i-1时使用递增后的i值，与伪逻辑中n-i-1（i为当前循环值）不符，应先计算n-i-1再执行i++。

3. 累加结果时使用错误的寄存器 #

原代码将$s0（catalan_recur(i)的结果）直接累加，实际需要先取出乘法结果再累加到$t1。

4. 临时寄存器$t2的保存问题 #

MIPS中t系列寄存器属于临时寄存器，递归调用会破坏其值，因此需要将$t2（循环变量i）存入栈中保存，避免被递归调用覆盖。

修正后的MIPS汇编代码 #

catalan_recur:
addi $sp,$sp,-16          # 增加栈空间，用于保存$t2
sw $ra,0($sp)
sw $s0,4($sp)
sw $a0,8($sp)
sw $t2,12($sp)            # 保存循环变量i到栈中
addi $t0,$0,1

bgt $a0,$t0,catalan_recur_else     #a0>1 ?
li $v0, 1
lw $t2,12($sp)             # 恢复$t2
lw $s0, 4($sp)
lw $ra, 0($sp)
addiu $sp, $sp, 16
jr $ra

catalan_recur_else:
  li $t1,0         #res=0
  li $t2,0         #i=0
catalan_recur_loop:  
  bge $t2, $a0, end_loop  # if i >= n, exit loop
   # res += catalan_recur(i)*catalan_recur(n-i-1)
  move $a0, $t2              
  jal catalan_recur          # call catalan_recur(i)        
  move $s0, $v0             # 保存catalan(i)到$s0
  lw $a0,8($sp)             # 恢复原n值
  # 先计算n-i-1，再递增i
  sub $a0,$a0,$t2            # n - i
  addi $a0,$a0,-1            # n - i -1
  jal catalan_recur          # call catalan_recur(n-i-1)
  # 计算乘法：catalan(i)*catalan(n-i-1)
  mult $s0, $v0
  mflo $t3                   # 取出乘法结果到$t3
  add $t1,$t1,$t3            # 累加到res
  addi $t2,$t2,1             # i++，此时再递增
  lw $a0,8($sp)              # 恢复原n值，准备下一次循环
  j catalan_recur_loop  
        
end_loop:
  move $v0, $t1               # move res to $v0
  lw $t2,12($sp)             # 恢复$t2
  lw $a0,8($sp)
  lw $s0,4($sp)        
  lw $ra, 0($sp)
  addiu $sp, $sp, 16
jr $ra

验证 #

修正后，输入0 1 2 3 6 9将得到预期输出1 1 2 5 132 4862。

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