using stack frame to push in parameters in order to calculate Fibbonnacci sequence but keep getting a 1 as a return value

Question

im working on a program that uses a stack frame in order to call functions recursively to help calculate the nth term of the fibonnacci sequence this is what i have so far but the output (which would be in register $t7 by the time the program stops running) returns 1. this is my progress so far

    .text
    .globl main
    
main:

    li  $v0, 4
    la  $a0, prompt
    syscall
    
    li  $v0, 5
    syscall






    addiu   $sp, $sp, -4
    sw  $t0, ($sp)
    addiu   $sp, $sp, -4
    sw  $t1, ($sp)
    addiu   $sp, $sp, -4            # space for parameters
    
    sw  $v0, ($sp)          # pushing parameter
    jal fib
    
    addiu   $sp, $sp, 4
    lw  $t1, ($sp)
    addiu   $sp, $sp, 4
    lw  $t0, ($sp)
    addiu   $sp, $sp, 4
    
    
    move    $t7, $v0
    
    li  $v0, 10
    syscall
    
fib:
    addiu   $sp, $sp, -4
    sw  $ra, ($sp)
    addiu   $sp, $sp, -4
    sw  $fp, ($sp)
    addiu   $sp, $sp, -4
    sw  $s0, ($sp)
    addiu   $sp, $sp, -4
    sw  $s1, ($sp)
    addiu   $fp, $sp, -8
    move    $sp, $fp
    
    lw  $t3, 24($fp)            # t3 = n of fib(int n)
    
    move    $s0, $t3
    li  $v0, 1              # return value 
    ble     $s0, 1, epilog          # 
    addi    $s0, $s0, -1            # setting up fib(n-1)
    jal fib
    move    $s0, $v0            # store fib(n-1)
    addi    $s0, $s0, -2            # set up fib(n-2)
    jal fib
    add     $v0, $s1, $v0           # add fib(n-1) and fib(n-2)
    
epilog:
    addiu   $sp, $fp, 8         # 
    lw  $s1, ($sp)
    addiu   $sp, $sp, 4
    lw  $s0, ($sp)
    addiu   $sp, $sp, 4
    lw  $fp, ($sp)
    addiu   $sp, $sp, 4
    lw  $ra, ($sp)
    jr  $ra
    
    
    
    li  $v0, 10
    syscall
    
    
    
    
    
    
    
    
    
    .data
    
prompt: .asciiz "enter a number dingus \n"
    

i feel like its my recursive function in the body of the subroutine, but ive been staring at this for the past couple hours and still have no idea what im doing wrong, any tips would be appreciated, thanks.

Answer 1

The first time you enter fib, after pushing your registers in the function prologue, the stack looks like this:

fp xx sp                         ;what values fp and sp point to. xx = nothing
xx xx s1 s0 fp ra t0 t1 v0       ;what registers were pushed. xx = nothing
00 04 08 12 16 20 24 28 32       ;offset n for "lw $r_,n($fp)

This chart is by no means standardized anywhere but it's a tool I like to use to visualize the stack frames of a function.

Then your function loads $s0 from 24(fp) which corresponds to the $t0 you pushed at the start. That's all well and good, but what happens for the fib(n-1) case? The function is called again, and the prologue is executed a second time. Now the stack looks like this:

fp xx sp 
xx xx s1 s0 fp ra xx xx s1 s0 fp ra t0 t1 v0
00 04 08 12 16 20 24 28 32 36 40 44 48 52 56

Do you see the problem now? Offset 24(fp) no longer points to your prior argument. So you're not loading the $s0 you pushed anymore when you recurse. Instead you're loading who knows what.

Now, if you moved this section inside the function, you'd be loading from the correct offset for your temporary variable.

    addiu   $sp, $sp, -4
    sw  $t0, ($sp)
    addiu   $sp, $sp, -4
    sw  $t1, ($sp)
    addiu   $sp, $sp, -4            # space for parameters 
    sw  $v0, ($sp)          # pushing parameter