MIPS Assembly - Trying to write a recursive program to calculate nCr (Combination)

Question

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

Answer 1

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

Answer 2

This code has so many errors it's hard to list. For starters, it has syntax errors and missing labels, so it doesn't even assemble. Then, the input values are never written into $t3 and $t4 because you got the operand order reversed. Furthermore, your CheckBounds uses JAL without saving $ra. Same goes for main. As for printing, the result is in $v0 so you need to save that before you clobber $v0 by printing the preceding stuff.

Fixing all those seems to make it work.

You should really learn to use a debugger/simulator to fix your bugs. For example, spotting that the registers don't have the expected values is easy.