MIPS Assembly MARS Program to Implement Recursion Assignment Solution.

.data

RECORDS: .space 1024

S:

.text

main:

 la $s7, S # load address of end of records in s7

 li $s0, 1 # first number to calculate

loop:

 move $a0, $s0 # pass number to subroutine

 jal zib # zib(i)

 # print number

 move $a0, $v0 # move return value to a0 to print it

 li $v0, 1 # syscall number to print integer

 syscall

 # print space

 li $a0, 32 # load ascii space value

 li $v0, 11 # syscall number to print character

 syscall

 addi $s0, $s0, 1 # increment number to calculate

 ble $s0, 20, loop # repeat while number is below or equal to 20

 # exit program

 li $v0,10 # syscall number to exit program

 syscall

#-------------------------------------------------------------------------------

# zib recursive subroutine, requires the number in a0, returns the result in v0

#-------------------------------------------------------------------------------

zib: # create new record in s7

 addi $s7, $s7, -12 # allocate space to save 3 registers

 sw $ra, 0($s7) # save ra in record

 sw $s0, 4($s7) # save s0 in record

 sw $s1, 8($s7) # save s1 in record

 bne $a0, $zero, else1 # if (n == 0)

 li $v0, 1 # return 1;

 j return

else1:

 bne $a0, 1, else2 # else if (n == 1)

 li $v0, 1 # return 1;

 j return

else2:

 bne $a0, 2, else3 # else if (n == 2)

 li $v0, 2 # return 2;

 j return

else3:

 andi $t0, $a0, 1 # else if (n%2 == 1 && n >= 3) // odd

 beq $t0, $zero, else4

 # return zib((n-1)/2) + zib((n-1)/2-1) + 1;

 addi $a0, $a0, -1 # n-1

 srl $a0, $a0, 1 # (n-1)/2

 move $s0, $a0

 jal zib # zib((n-1)/2)

 move $s1, $v0 # save result in s1

 addi $a0, $s0, -1 # (n-1)/2 -1

 jal zib # zib((n-1)/2-1)

 add $v0, $v0, $s1 # zib((n-1)/2) + zib((n-1)/2-1)

 addi $v0, $v0, 1 # zib((n-1)/2) + zib((n-1)/2-1) + 1

 j return

else4: # else if (n%2 == 0 && n >= 4) // even

 # return zib(n/2) + zib(n/2+1) + 1;

 srl $a0, $a0, 1 # n/2

 move $s0, $a0

 jal zib # zib(n/2)

 move $s1, $v0 # save result in s1

 addi $a0, $s0, 1 # n/2 +1

 jal zib # zib(n/2+1)

 add $v0, $v0, $s1 # zib(n/2) + zib(n/2+1)

 addi $v0, $v0, 1 # zib(n/2) + zib(n/2+1) + 1

return:

 # load old values from record and remove it

 lw $ra, 0($s7) # load ra from record

 lw $s0, 4($s7) # load s0 from record

 lw $s1, 8($s7) # load s1 from record

 addi $s7, $s7, 12 # remove space allocated for the record

 jr $ra # return to caller