Catalan numbers in MIPS assembly

Question

Catalan numbers are recursively defined by the following equation.

This is the test case:

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

So my output is wrong when n = 3, the output should be 5 and mine is 4, and so on. here are my code:

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

pseudocode:

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: the argument for the given positive integer input, n

I know I got wrong in the catalan_recur_loop, and the addition must miss some numbers, but I can't figure out how to fix the errors.

Answer 1

The registers $t1 and $t2 are caller-save, so you have to save their values (on the stack) before calling functions inside functions not to lose the values.

Saving may be done like this:

  sw $t1,12($sp) # save $t1
  sw $t2,16($sp) # save $t2
  jal catalan_recur
  lw $t1,12($sp) # restore $t1
  lw $t2,16($sp) # restore $t2

Also don't forget to allocate the space to save on the stack (add/subtract 20 instead of 12 from the stack pointer)

Answer 2

That function is saving and restoring s0 for the benefit of the caller, ra for the benefit itself - so it knows where to return to, but saving a0 and restoring it isn't benefitting anyone. Like ra, a0 belongs to the called function, the caller has no expectations on them, unlike with s registers.

You have correctly determined that an s register can be used to preserve a return value from one call that is needed after another call, however, n initially in a0, i, and res, each also merit their own s registers.

For n, initially in a0, copy it to an s register in prologue, of course, after preseving the original value in that s register.

Answer 3

Everything looks good but you should add mflo $s0 below mult $s0, $v0, since the result is returning not returning the lower 32 bits.

Answer 4

The issue was the result from the recursive did not pass back becuase of the $t register. I expanded the stack, and saved the result into the stack, and load it back and get the final value.

catalan_recur:
    addi $sp, $sp, -20   # Allocate space on stack for 5 items: $ra, $s0, $s1, $a0, and loop counter
    sw $ra, 0($sp)       # Save return address
    sw $s0, 4($sp)       # Save $s0 (we will use it for temporary storage)
    sw $s1, 8($sp)       # Save $s1 (used for accumulating result)
    sw $a0, 12($sp)      # Save original argument $a0 (n)
    sw $t2, 16($sp)      # Save $t2 if used before calling this function

    li $t0, 1            # Load immediate 1 into $t0 for comparison
    li $s1, 0            # Initialize accumulator for result in $s1

    ble $a0, $t0, return_one # If n <= 1, return 1 as Catalan number

    # Initialize loop counter, $t2 = 0
    li $t2, 0

loop_start:
    blt $t2, $a0, recursive_part # If $t2 < n, continue recursion
    j end_loop                   # Else, end loop

recursive_part:
    move $a0, $t2                # Prepare first argument for recursive call
    jal catalan_recur            # Recursive call catalan_recur(i)
    move $s0, $v0                # Store the result of catalan_recur(i) in $s0

    lw $a0, 12($sp)              # Restore $a0 (n) for calculation of n-i-1
    sub $a1, $a0, $t2            # n - i
    addi $a1, $a1, -1            # n - i - 1
    move $a0, $a1                # Prepare second argument for recursive call
    jal catalan_recur            # Recursive call catalan_recur(n-i-1)

    mul $s0, $s0, $v0            # Multiply results: catalan_recur(i) * catalan_recur(n-i-1)
    add $s1, $s1, $s0            # Accumulate in $s1

    lw $a0, 12($sp)              # Restore $a0 for next iteration
    addi $t2, $t2, 1             # Increment loop counter
    j loop_start                 # Jump back to start of loop

end_loop:
    move $v0, $s1                # Move accumulated result to $v0
    j cleanup                    # Jump to cleanup

return_one:
    li $v0, 1                    # Set return value to 1 for base case

cleanup:
    lw $ra, 0($sp)               # Restore $ra
    lw $s0, 4($sp)               # Restore $s0
    lw $s1, 8($sp)               # Restore $s1
    lw $a0, 12($sp)              # Restore $a0
    lw $t2, 16($sp)              # Restore $t2
    addi $sp, $sp, 20            # Deallocate stack space
    jr $ra                       # Return