title: MIPS Recursive Fibonacci Sequence
body: <p>I'm having trouble dealing with stacks recursively in MIPS. I get the concept, but my program isn't reacting as I mean it to.</p>
  
  <p>My goal is to take user input as n and print the Fibonacci number at n. What I have so far is below.</p>
  
  <p>(I'm fairly certain the problem is in the actual calculation of the number in the fib function.) Thanks for any help! :)</p>
  
  <pre><code>.text
  main:
  # Prompt user to input non-negative number
  la $a0,prompt
  li $v0,4
  syscall
  li $v0,5
  syscall
  move $t2,$v0
  
  
  # Call function to get fibonnacci #n
  move $a0,$t2
  move $v0,$t2
  jal fib
  move $t3,$v0
  
  # Output message and n
  la $a0,result
  li $v0,4
  syscall
  move $a0,$t2
  li $v0,1
  syscall
  la $a0,result2
  li $v0,4
  syscall
  move $a0,$t3
  li $v0,1
  syscall
  la $a0,endl
  li $v0,4
  syscall
  
  # End program
  li $v0,10
  syscall
  
  fib:
  # Compute and return fibonacci number
  beqz $a0,zero
  beq $a0,1,one
  sub $sp,$sp,4
  sw $ra,0($sp)
  sub $a0,$a0,1
  
  jal fib
  
  lw $ra,0($sp)
  add $sp,$sp,4
  sub $t8,$v0,2 # n - 2
  sub $t9,$v0,1 # n - 1
  add $v0,$t8,$t9 # add n-2,n-1
  jr $ra # decrement/next in stack
  
  zero:
  li $v0,0
  jr $ra
  one:
  li $v0,1
  jr $ra
  
  .data
  prompt: .asciiz "Enter a non-negative number: "
  result: .asciiz "F_"
  result2: .asciiz " = "
  endl: .asciiz "\n"
  </code></pre>
  
  <p>Example runs:</p>
  
  <pre><code>Enter a non-negative number: 5
  F_5 = -29
  
  Enter a non-negative number: 6
  F_6 = -61
  </code></pre>
  
  <p>Correct runs:</p>
  
  <pre><code>Enter a non-negative number: 5
  F_5 = 5
  
  Enter a non-negative number: 6
  F_6 = 8
  </code></pre>