I'm trying to create a mips assembly program to calculate nCr recursively.
I've written the whole program, including a driver, but It's not functioning correctly. All of my inputs and outputs work but my recursive algorithm is returning crazy numbers. For example, nCr ==268501120 instead of 10.
Updated code: http://pastebin.com/52ueQu99
Here's just a snippet of my algorithm:
nCk:
sub $sp, $sp, 16 #allocate the needed space in stack.
sw $ra, 0($sp) #save return address in first position
sw $t3, 4($sp) #save n in the stack
sw $t4, 8($sp) #save k in the stack
sub $t3, $t3, 1 #Subtract one from n
sub $t4, $t4, 1 #Subtract one from k
jal checkBounds #Check for end of recursion.
sw $v0, 12($sp) #copy returned 1 or 0 into stack.
lw $t3, 4($sp) #Load original n back into t3.
lw $t4, 8($sp) #Load original k back into t4.
sub $t3, $t3, 1 #Subtract one from n again. (n-1 step of recursive algorithm)
jal checkBounds #Check for end of recursion with n 1 number lower.
lw $t2, 12($sp) #Load the value held in the previously returned v0.
add $v0, $v0, $t2 #Add old returned value to new returned value.
lw $ra, 0($sp) #Load the original return address.
addi $sp, $sp, 16 #Add 16 more bytes to the stack.
jr $ra
checkBounds: #Check if program should still recurse
beq $t3, $t4, return1 #If n==k
beq $t4, $0, return1 #if k==0
li $v0, 0 #If (j!=k || k!=0){ return 0};
jal nCk
jr $ra
return1: #Returns 1
li $v0, 1
jr $ra
I took the liberty of refactoring your code a little and skipping error checking part to show you the most important parts. Essentially I have implemented iterative factorial procedure that does not do any error checking on input value. Then in the main program I get inputs from the user, compute factorials and apply the formula. Hope that helps.
.data
enterN: .asciiz "Please enter the n value: \n"
enterK: .asciiz "Please enter the k value: \n"
output: .asciiz "Result is: "
.text
j main
factorial:
# iterative factorial procedure
# $a0 - number, no error checking is performed on input
# $v0 - factorial of the number
addi $sp, $sp, -4
sw $ra, 0($sp)
li $v0, 1
li $s0, 1
factorial_begin:
beq $s0, $a0, factorial_end # n == 1?
mul $v0, $v0, $a0 # $v0 = $v0 * n
subi $a0, $a0, 1 # n = n - 1
j factorial_begin
factorial_end:
lw $ra, 0($sp)
addi $sp, $sp, 4
jr $ra
main:
# compute cobination (n choose k) = n! / k!(n-k)!
# ----------------------------------------------
la $a0, enterN #Ask for the first param, n.
li $v0, 4 #String syscall
syscall #Prints out string.
li $v0, 5
syscall #Places inputted value in v0.
la $t0, ($v0) # $t0 = n
# computer factorial of n
move $a0, $t0
jal factorial
move $t1, $v0 # $t1 = n!
la $a0, enterK #Asks for the second param, k.
li $v0, 4 #String syscall
syscall #Prints out string
li $v0, 5
syscall #Places inputted value in v0.
la $t2, ($v0) # $t2 = k
# computer factorial of k
move $a0, $t2
jal factorial
move $t3, $v0 # $t3 = k!
sub $a0, $t0, $t2 # $a0 = n - k
jal factorial
move $t4, $v0 # $t4 = (n-k)!
mul $t3, $t3, $t4 # $t3 = k! * (n-k)!
div $t1, $t1, $t3 # $t1 = n! / (k! * (n-k)!)
# print out the result
la $a0, output
li $v0, 4
syscall
move $a0, $t1
li $v0, 1
syscall