Hey I'm using MIPS and created a Fibonacci program and am not sure that its working correctly. When I enter 1 it returns 1 like it should and when I enter 0 it returns 0 like it should. However when I enter a number that takes it into the Fibonacci sequence I think its returning the wrong number. The Fibonacci formula is F(n-1) + F(n-2), so when I enter 3 shouldn't it return 3 as the Fibonacci number? because my program returns 2 as the Fibonacci number and I can't figure out where I went wrong. Maybe someone can tell me

``````# Code with subroutine to compute Fibonacci number recursively
# Uses system stack

.data
in_string:	.asciiz		"Input a positive integer:\n\n"
out_string:	.asciiz		"The Fibonacci number is:\n\n"

.text
main:
# print out prompt
li	\$v0, 4			# system call code for printing string = 4
la	\$a0, in_string		# load address of string to be printed into \$a0
syscall				# call operating system to perform print operation

li	\$v0, 5			# system call code for read integer = 5
syscall				# call operating system
move	\$s0, \$v0		# value read from keyboard returned in register \$v0; transfer to \$s0

sw	\$s0,(\$sp)		# push argument for Fib on stack
addi	\$sp,\$sp,-4		#   and decrement stack pointer
addi	\$sp,\$sp,4		# increment stack pointer
lw	\$s1,(\$sp)		#   and pop result from stack

# print out prompt
li	\$v0, 4			# system call code for printing string = 4
la	\$a0, out_string		# load address of string to be printed into \$a0
syscall				# call operating system

# print out result (stored in \$s1)
li	\$v0, 1			# system call code for printing integer = 1
move	\$a0, \$s1		# move integer to be printed into \$a0:  \$a0 = \$s1
syscall				# call operating system to perform print

# exit program
li	\$v0, 10			# system call code for exit = 10
syscall				# call operating system

# blank line at end to keep SPIM happy!

##################################################################################
# Fibonacci subroutine
# input:  integer n, on stack
# output: Fib(n), nth Fibonacci number
# description: recursively computes   Fib(n)  =  Fib(n-1) + Fib(n-2),  Fib(0) = 0, Fib(1) = 1.
# uses: \$t0, \$t1
##################################################################################

Fib:
# procedure prologue:
sw	\$ra,(\$sp)		# save return address on stack, since recursive,
addi	\$sp,\$sp,-4		#   and decrement stack pointer
sw	\$fp,(\$sp)		# save previous frame pointer on stack
addi	\$sp,\$sp,-4		#   and decrement stack pointer
add	\$fp,\$sp,12		# set frame pointer to point at base of stack frame

lw	\$t0,(\$fp)		# copy argument to \$t0:  \$t0 = n
bge	\$t0, 2 ,do_recurse	# if argument n >= 2, branch to recursive sequence
beq	\$t0, 0, base_0		# if n = 0, jump to base_0
beq	\$t0, 1, base_1		# if n = 1, jump to base_1

base_0:
li \$t0, 0			# else set result to 0
b epilogue			# branch to end

base_1:
li	\$t0, 1			# else set result to 1
b	epilogue		# branch to end

do_recurse:	addi	\$t0,\$t0,-1		# \$t0 = n-1
sw	\$t0,(\$sp)		# push argument n-1 on stack
addi	\$sp,\$sp,-4		#   and decrement stack pointer
jal	Fib			# call Fibonacci with argument n-1
# leave result on stack for now
lw	\$t0,(\$fp)		# re-copy argument to \$t0:  \$t0 = n
addi	\$t0,\$t0,-2		# \$t0 = n-2
sw	\$t0,(\$sp)		# push argument n-2 on stack
addi	\$sp,\$sp,-4		#   and decrement stack pointer
jal	Fib			# call Fibonacci with argument n-2
addi	\$sp,\$sp,4		# increment stack pointer
lw	\$t0,(\$sp)		#   and pop result of Fib(n-2) from stack into \$t0
addi	\$sp,\$sp,4		# increment stack pointer
lw	\$t1,(\$sp)		#   and pop result of Fib(n-1) from stack into \$t1
add	\$t0,\$t0,\$t1		# \$t0 = Fib(n-2) + Fib(n-1); have result

epilogue:					# procedure epilogue: \$t0 holds result
addi	\$sp,\$sp,4		# increment stack pointer
lw	\$fp,(\$sp)		#   and pop saved frame pointer into \$fp
addi	\$sp,\$sp,4		# increment stack pointer
lw	\$ra,(\$sp)		#   and pop return address into \$ra
addi	\$sp,\$sp,4		# increment stack pointer
#   to pop argument (n) from stack (discard)
sw	\$t0,(\$sp)		# push result onto stack
addi	\$sp,\$sp,-4		#   and decrement stack pointer