我在将 C 代码转换为组合函数 (nCr) 的 MIPS 汇编代码时遇到问题。
nCr = (n-1Cr-1) + (n-1Cr)
当我将 int 5 用于 n,将 3 用于 r(数字数据)时,结果必须为 10。
我想使用递归和堆栈指针,但我遇到堆栈溢出错误。
我的 MIPS 代码如下。
我的代码有什么问题?
我不能很好地识别问题...
##data
.data
digit: .word 5, 3
.text
.globl main
main:
##load data
la $t0, digit
lw $a0, 0($t0) #put 5 in a
lw $a1, 4($t0) #put 3 in b
##call Function comb
jal comb
##save return value in $t1
move $t1, $v0
##print result
li $v0, 1
add $a0, $0, $t1
syscall
##exit
li $v0, 10
syscall
##Function int comb(int a, int b)
comb:
addi $sp, $sp, -8
sw $ra, 4($sp)
sw $s0, 0($sp)
##base case
bne $a0, $a1, gen #if (a==b)
addi $v0, $0, 1 #$v0 (1)
j rtn
bne $a1, $0, gen #if (b==0)
addi $v0, $0, 1 #$v0 (1)
j rtn
##recursive call
gen:
addi $a0, $a0, -1 #$a0 (a-1)
addi $a1, $a1, -1 #$a1 (b-1)
jal comb #call comb(a-1, b-1)
add $s0, $v0, $0 #$s0 comb(a-1, b-1)
addi $a1, $a1, 1 #$a1 (b)
jal comb #call comb(a-1, b)
add $v0, $v0, $s0 #$v0 (comb(a-1, b-1) + comb(a-1, b))
j rtn
rtn:
lw $s0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
jr $ra
.end
最佳答案
您的代码存在多个问题。
首先,您选择的递归关系效率很低,而且比必要的复杂得多。连Wikipedia有几个比较好的递归关系,例如
n 超过 k = (n-1 超过 k-1) * (n/k)
避免多次递归到函数中(从而允许以尾递归方式编写函数)。
您使用的循环还有一个额外的缺点,即您必须同时检查 k==0
和 k==n
。
这将我们带到您的实现中,它未能正确检查这两个条件:
##base case
bne $a0, $a1, gen #if (a==b)
addi $v0, $0, 1 #$v0 (1)
j rtn
bne $a1, $0, gen #if (b==0)
addi $v0, $0, 1 #$v0 (1)
j rtn
如果 a!=b
,无论 b==0
是否存在,第一个测试都会跳过第二个测试,因此第二个测试无法访问。您必须将代码更改为
##base case
bne $a0, $a1, isbzero #if (a==b)
addi $v0, $0, 1 #$v0 (1)
j rtn
isbzero:
bne $a1, $0, gen #if (b==0)
addi $v0, $0, 1 #$v0 (1)
j rtn
最后,在递归调用之前不保留函数参数的值。如果您想符合 ABI,则不能假定函数参数寄存器中的值在整个调用过程中都得到保留。
特别是之后
##recursive call
gen:
addi $a0, $a0, -1 #$a0 (a-1)
addi $a1, $a1, -1 #$a1 (b-1)
jal comb #call comb(a-1, b-1)
以下
add $s0, $v0, $0 #$s0 comb(a-1, b-1)
addi $a1, $a1, 1 #$a1 (b)
jal comb #call comb(a-1, b)
$a0
和 $a1
的值不正确。
如果 ABI 合规性对您来说不重要,您可以在返回之前通过再次递增参数来恢复值。
关于将 C 代码转换为 MIPS 汇编 - 使用递归的组合函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52747125/