I have a problem with conversing C code to MIPS assembly code of combination function (nCr).
nCr = (n-1Cr-1) + (n-1Cr)
and when I put int 5 for n and 3 for r (digit data), the result has to be 10.
I want to use the recursion and stack pointer, but I have an error with stack overflow.
I have my MIPS code below.
What's wrong with my code?
I cannot recognize the problem well...
##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
There are multiple problems with your code.
First, the recurrence relation you have chosen is very inefficient and much more complicated than necessary. Even Wikipedia has several better recurrence relations, for example
n over k = (n-1 over k-1) * (n/k)
avoids recursing into the function multiple times (thus allowing the function to be written tail-recursively).
The recurrence you are using has the additional disadvantage that you must both check for k==0 and k==n.
This brings us to your implementation, which fails to check both conditions correctly:
##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
The first of these tests jumps over the second test if a!=b, regardless of whether b==0, so the second test is unreachable. You would have to change the code to
##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
Finally, you do not preserve the values of the function arguments before the recursive calls. If you want to be ABI compliant, you cannot assume the values in the function argument registers are preserved across the call.
In particular after
##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)
the following
add $s0, $v0, $0 #$s0 comb(a-1, b-1)
addi $a1, $a1, 1 #$a1 (b)
jal comb #call comb(a-1, b)
will have incorrect values for $a0 and $a1.
If ABI compliance does not matter to you, you could restore the values before returning by incrementing the arguments again.