+1 (315) 557-6473 

MIPS Assembly MARS Program to Implement Recursion Assignment Solution.


Write an assembly language program to implement recursion in a program.

Requirements and Specifications

Below is a variation of a Fibonacci sequence, not an original. Many such variations exist.
Implement the below function using the MARS Mips assembler. Call the function repeatedly to produce the output as shown below. For your convenience you are given the function in symbolic and C code.
This is a weird rendition of Fibonacci which tends to calculate results which appear to zig and zag.
zib(0) = 1
zib(1) = 1
zib(2) = 2
zib(2n+1) = zib(n) + zib(n-1) + 1, if n>0 (odd values 3 and higher)
zib(2n) = zib(n) + zib(n+1) + 1, if n>1 (even values 4 and higher)
The C program to calculate this looks like:
Part B
Written portion: Using your student number which will appear in the following format, abcDEFG. This will produce the two base 10 numbers, D.E x 102, and F.G x 103. Take your student number and substitute in the digits as shown above. Using the FPS website (see course home page) convert each over to a normalized binary form. Each should look something like 1.xxxxxxxx * 2y. Depending on your student number, the number of significant digits will vary.
For those students who have DE and/or FG equal to zero, i.e. 0.0x102, then substitute 34 for any occurrence of 00 to ensure a non-zero term.
Using the FPS multiplication shown in class, multiply the above numbers together, producing a FPS result. Show all work, that is where the marks are. You can verify your work by doing a base 10 multiplication and using the FPS website to verify the binary result.
Screenshots of output
assembly language in MIPS to run recursion Mips assembly

 Source Code


RECORDS: .space 1024




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

 li $s0, 1 # first number to calculate


 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


 # print space

 li $a0, 32 # load ascii space value

 li $v0, 11 # syscall number to print character


 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



# 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


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

 li $v0, 1 # return 1;

 j return


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

 li $v0, 2 # return 2;

 j return


 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


 # 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