I'm really new to MIPS, so I'm having a hard time reading and understanding the code. For my homework, I was asked to identify and corrects errors in the folllowing code which computes the fibonacci number with given n passed in register \$a0, and return it in \$v0. I was most of the time lost in the middle, while trying to to follow the flow control ... Could you help me figure out the errors? Or just simply help me with the actual correct piece of code, so I can work on that and find the errors in this one.

``````FIB:      addi \$sp, \$sp, –12
sw \$ra, 0(\$sp)
sw \$s1, 4(\$sp)
sw \$a0, 8(\$sp)
slti \$t0, \$a0, 1
beq \$t0, \$0, L1
j EXIT
jal FIB
jal FIB
EXIT:     lw \$ra, 0(\$sp)
lw \$a0, 8(\$sp)
lw \$s1, 4(\$sp)
jr \$ra
``````

## All 5 Replies

``````FIB:
# make stack frame
sw \$ra, 0(\$sp)    # return address
sw \$s1, 4(\$sp)    # temporary storage?
sw \$a0, 8(\$sp)    # parameter

# Check if bottom of recursion
slti \$t0, \$a0, 1
beq \$t0, \$0, L1   # = bne \$a0, \$0, L1: if param == 0, continue, else goto L1
addi \$v0, \$a0, \$0 # Move param to v0
j EXIT

L1:
# Call FIB(param - 1)
jal FIB       # What, do you think, happens to v0 here?

# store v0 to s1

# Call FIB(param - 2)
jal FIB

# restore v0 from s1

# Delete stack frame and eturn fron call
EXIT:     lw \$ra, 0(\$sp)    # return address
lw \$a0, 8(\$sp)    # parameter
lw \$s1, 4(\$sp)    # temporary storage?
jr \$ra
``````

The comments that turboscrew put in your code should help. Computing fibonacci sequences is typically done with a recursive algorithm. IE: fib(x) = fib(x-1) + fib(x-2) with x==1 being the limiting factor that causes the loop to terminate. IE, fib(1) == 1, and fib(0) == 0, so fib(2) == 1 (fib(1) + fib(0)), and fib 3 == 2 (fib(2) + fib(1)), and fib(4) == 3 (fib(3) + fib(2)), fib(5) == 5, fib(6) == 8, fib(7) == 13, etc. ad infinitum... :-)