#Maura Dailey CSE 331
#Recursive Fibonacci Algorithm One
#
#  int fib(int n) {
#    if(n==0)
#      return 0;
#    else if(n==1)
#      return 1;
#    else
#      return fib(n-1) + fib(n-2);
#

.data
.align 0					  #turn off automatic alignment
str1: .asciiz "Enter Number: " #create a null terminated ascii string
str2: .asciiz "The answer is: "			  #create another one
str3: .asciiz "\n"				  #and another
.text
.align 2
.globl main					  #following is global

fib:	addi $sp, $sp, -12		#Decrement $sp to make room for variables
	sw $ra, 8($sp)			#Save $ra in memory
	sw $a0, 4($sp)			#Save $a0 in memory
	sw $t0, 0($sp)			#Save $t0 in memory

	bne $a0, $zero, fib1		#If $a0 != 0, skip the following

	add $v0, $zero, $zero		#If $a0 == 0, return 0
	addi $sp, $sp, 12		#Restore $sp
	jr $ra				#Return to whence thy came!

fib1:	addi $t1, $zero, 1		#We need a comparison with a 1 

	bne $a0, $t1, fib2		#If $a0 != 1, skip the following

	add $v0, $t1, $zero		#If $a0 == 1, return 1
	addi $sp, $sp, 12		#Restore $sp
	jr $ra				#We're done here, so return

fib2:	addi $a0, $a0, -1		#Decrement n
	jal fib				#Call fib(n-1)

	add $t0, $v0, $zero		#Here, we save fib(n-1) from certain destruction
	addi $a0, $a0, -1		#Decrement n
	jal fib				#Call fib(n-2)

	add $v0, $v0, $t0		#Add fib(n-1) + fib(n-2)

return:	lw $t0, 0($sp)			#Restore $t0 from memory
	lw $a0, 4($sp)			#Restore $a0 from memory
	lw $ra, 8($sp)			#Restore $ra from memory
	addi $sp, $sp, 12		#Restore $sp
	jr $ra				#Return to caller


main:	li $v0, 4		#prepare $v0 with a syscall instruction
	la $a0, str1		#load the first string into $a0 to provide an argument for syscall
	syscall			#invoke syscall operation 4, printing str1 to the console 

	li $v0, 5		#load a new syscall instruction into $v0
	syscall			#invoke syscall operation 5, storing an integer from input

	addi $a0, $v0, 0	#move the entered integer into $a0

	jal fib			#call our procedure

	add $s0, $v0, $zero	#save our results

	li $v0, 4		#load a new syscall instruction into $v0
	la $a0, str2		#load the second string into $a0
	syscall			#invoke syscall operation 4, printing str2 to the console

	li $v0, 1		#load a new syscall instruction into $v0
	add $a0, $s0, $zero	#load the results of our procedure into $a0
	syscall			#invoke syscall operation 1, printing $a0 to the console

	li $v0, 4		#load a new syscall instruction into $v0
	la $a0, str3		#load the third string into $a0 
	syscall			#invoke syscall operation 4, printing str3 to the console