Using Recursive Functions to Implement Fibonacci Sequence Algorithm
.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
jalzib # 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
jalzib # zib((n-1)/2)
move $s1, $v0 # save result in s1
addi $a0, $s0, -1 # (n-1)/2 -1
jalzib # 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
jalzib #zib(n/2)
move $s1, $v0 # save result in s1
addi $a0, $s0, 1 # n/2 +1
jalzib # 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