.data
enter: .asciiz "Enter the index of the number in the Fibonacci sequence you would like to compute: "
res: .asciiz "The number is "

	.text
main:
	# Prompt
	li $v0, 4
	la $a0, enter
	syscall

	# Read value
	li $v0, 5
	syscall

	# Call Fibonacci
	la $a0, ($v0)
	jal fib

	# Print result
	la $t0, ($v0)
	li $v0, 4
	la $a0, res
	syscall
	li $v0, 1
	la $a0, ($t0)
	syscall

	j done

# fib(0) = 0
# fib(1) = 1
# fib n = fib (n - 1) + fib (n - 2)
fib: 	addi $sp, $sp, -12
	sw $ra, 0($sp) # Store addr
	sw $a0, 4($sp) # Store n
	sw $s0, 8($sp) # Store last first fib

	# Check if n is 0
	bnez $a0, fib1
	# If it is, return 0
	la $v0, ($zero)
	j fret

fib1:	# Check if n is 1
	bne $a0, 1, fib2
	# If it is, return 1
	addi $v0, $zero, 1
	j fret

fib2:	# Otherwise, we need to recursively add
	addi $a0, $a0, -1 # n - 1
	jal fib
	la $s0, ($v0) # fib(n - 1)

	addi $a0, $a0, -1 # n - 2
	jal fib
	la $t1, ($v0) # fib(n - 2)

	add $v0, $s0, $t1 # fib(n - 1) + fib(n - 2)

fret:	lw $ra, 0($sp) # Restore addr
	lw $a0, 4($sp) # Restore n
	lw $s0, 8($sp) # Restore last fib
	addi $sp, $sp, 12 # Restore sp

	jr $ra # Return

done: