title: What is wrong with MIPS Fibonacci Recursion?
body: <p>I am working in converting a fibonacci function written in C to MIPS. My MIPS code is currently not working and I can not identify the issue. I am new to assembly and I hope you can help me identifying the main problem in my MIPS code. Look at my function fibonacci under my MIPS code. When I compile my MIPS code I get the following error : "Can't expand stack segment by 24 bytes to 5242888 bytes.</p>
  
  <p>I have a C code as following:</p>
  
  <pre class="lang-or-tag-here prettyprint-override"><code>int fib(int n) {
      if (n == 0) {
          return 0;
      } else if (n == 1) 
      {
          return 1;
      }
      return fib(n-1) + fib(n-2);}
  </code></pre>
  
  <p>I have my MIPS as following:</p>
  
  <pre><code>        .text
              .globl main
      main:
  
  
   subu $sp,$sp,32         # Stack frame is 32 bytes long
          sw $ra,20($sp)          # Save return address
          sw $fp,16($sp)          # Save old frame pointer
          addiu $fp,$sp,28        # Set up frame pointer
  
          li $a0,10               # Put argument (10) in $a0
          jal fibonacci                # Call fibonacci function
          move $t0,$v0            # Move fact result to $t0 (temporary)
          la $a0,$LC              # Put format string in $a0
          li $v0, 4               # System call code for print_str
          syscall                 # Make system call
          move $a0, $t0           # Move $t0 fibonacci result to $a0 (argument)
          li $v0, 1               # System call code for print_int
          syscall                 # Make system call
          #jal printf              # Call the print function
  
          lw $ra,20($sp)          # Restore return address
          lw $fp,16($sp)          # Restore frame pointer
          addiu $sp,$sp,32        # Pop stack frame
          jr $ra                  # Return to caller
  
          .rdata
  $LC:
          .ascii "The fibonacci of 10 is "
  
      .text
  fibonacci:
          subu $sp,$sp,32         # Stack framee is 32 bytes long
          sw $ra,20($sp)          # Save return address
          sw $fp,16($sp)          # Save frame pointer
          addiu $fp,$sp,28        # Set up frame pointer
          sw $a0,0($fp)           # Save argument (n)
          sw $a1,4($fp)
  
          lw $v0,0($fp)           # Load n
          li $v0,1                # Return 1
  
          # a0 = n
          # v0 = return_value 
  
          move $s0, $a0           #put n in $s0
          bne $s0, $0, not_zero   # if n doesn't equal to zero go to else if
          add $v0, $0, 0          # set return value to zero 
          j exit                  #go to exit
  
  not_zero:
          li    $t0, 1                # assigning t0 to 1
          bne   $s0, $t0, test_two    # if no equal to one go to the else
          add   $v0, $0, 1            # set return value to one
          j exit                      # go to exit
  
  test_two:
  
          addi $a0, $s0, -1   # assign $a0 = n -1
          jal fibonacci
          move $s1, $v0
  
          addi  $a0, $s0, -1  # assign $a0 = n -1
          jal fibonacci
          add   $v0, $s1, $v0 # Add f_(n-1) + f_(n-2)
          j exit
  
  exit:                           # Result is in $v0
          lw $ra, 20($sp)         # Restore $ra
          lw $fp, 16($sp)         # Restore $fp
          addiu $sp, $sp, 32      # Pop stack
          jr $ra                  # Return to caller
  </code></pre>