#Maura Dailey CSE 331
#Recursive Fibonacci Algorithm Two
#
# int fib_iter(int a, int b, int count) {
#   if (count==0)
#     return b;
#   else
#     return fib_iter(a+b,a,count-1);
#

.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_iter:	addi $sp, $sp, -12		#Decrement $sp to make room for variables
		sw $ra, 12($sp)			#Save $ra in memory
		sw $a2, 8($sp)			#Save $a2 in memory (count)
		sw $a1, 4($sp)			#Save $a1 in memory (b)
		sw $a0, 0($sp)			#Save $a0 in memory (a)

		bne $a2, $zero, fib_iter2	#If $a2 != 0, skip the following

		add $v0, $a1, $zero		#If $a2 == 0, return b
		addi $sp, $sp, 12		#Restore $sp
		jr $ra				#Return to caller

fib_iter2:	addi $a2, $a2, -1		#Decrement $a2 (count)
		add $t0, $zero, $a0		#Temporarily store $a0 (a)
		add $a0, $a0, $a1		#Store $a0 + $a1 in $a0
		add $a1, $zero, $t0		#Move $a0's old value to b
		jal fib_iter			#Call fib_iter(a+b, b, count-1)

fib_return:	lw $a0, 0($sp)			#Restore $a0 from memory
		lw $a1, 4($sp)			#Restore $a1 from memory
		lw $a2, 8($sp)			#Restore $a2 from memory
		lw $ra, 12($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 $a2, $v0, 0	#move the entered integer into $a2 (count)
	addi $a0, $zero, 1 	#set $a0 to 1
	add $a1, $zero, $zero	#set $a1 to 0
	jal fib_iter		#call fib_iter(1,0,count)

	add $s0, $v0, $zero	#store the results in $s0

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

	li $v0, 1		#prepare $v0 with a syscall instruction
	add $a0, $s0, $zero	#load the results from $s0 into $a0
	syscall			#invoke syscall operation 1, printing an integer to the console

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