        .text
# $a0: Which value in the sequence we want, starting with 0 (unsigned)
# $v0: result
#
# fib(0) = 0
# fib(1) = 1
# fib(n) = fib(n - 1) + fib(n - 2)
fibonacci:
        # check for a base case
        beq $a0, $zero, is_zero
        li $t0, 1
        beq $a0, $t0, is_one

        # if we get here, we don't have a base case
        
        # s0: n
        # s1: fib(n - 1)
        # This requires saving $s0, $s1, and $ra.
        # s registers are used because we need these values to
        # exist beyond the call.

        # make some space, and save the registers
        addi $sp, $sp, -12
        sw $s0, 8($sp)
        sw $s1, 4($sp)
        sw $ra, 0($sp)

        # put n in $s0
        move $s0, $a0
        
        # calculate fib(n - 1), putting result in $s1
        addi $a0, $s0, -1
        jal fibonacci
        move $s1, $v0

        # now calculate fib(n - 2)
        addi $a0, $s0, -2
        jal fibonacci

        # calculate final result
        addu $v0, $s1, $v0

        # restore registers
        lw $s0, 8($sp)
        lw $s1, 4($sp)
        lw $ra, 0($sp)
        addi $sp, $sp, 12

        # return to caller
        jr $ra
is_zero:
        li $v0, 0
        jr $ra
is_one:
        li $v0, 1
        jr $ra
        
main:
        # number to calculate
        li $a0, 6
        jal fibonacci

        # print out the number
        move $a0, $v0
        li $v0, 1
        syscall

        # exit
        li $v0, 10
        syscall
        
