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
# read integer into $s0
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
jal Fib # jump to subroutine
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
jr $ra # return to caller
##################################################################################
# end of Fibonacci
##################################################################################