#f(n) = 2f(n - 1) + 3f(n - 2)+ 1
#f(0) = 1
#f(1) = 2

li $a0, 3 #       THIS IS THE INPUT NUMBER N
li $t2, 3 #        this is the 3 in 3f(n-2)
jal f
move $a0, $v0     #move result to a0
li $v0, 1         #print result
syscall
li $v0, 10        #end
syscall
# $a0 = n
f:
add $sp, $sp, -8 ############### RESERVE SPACE ON THE STACK
sw $a0, 0($sp)
sw $ra, 4($sp)

beq $a0, 0, BASECASE1 ########### DO THE THING
beq $a0, 1, BASECASE2
addi $a0, $a0, -1 ###### N - 1
jal f

addi $sp, $sp, -4
sw $v0, 0($sp)              ##########store v0 on stack
addi $a0, $a0, -1        ##### n - 2
jal f                    #### f(n-2)

lw $t0, 0($sp) #load f(n-1) to t0
sll $t0, $t0, 1 #multiply that by 2
mult $v0, $t2 # multiply f(n-2) by 3
mflo $v0 # store in v0
add $v0, $v0, $t0 # add 2f(n-1) + 3f(n-2)
addi $v0, $v0, 1 # ADD 1
addi $sp, $sp, 4
j RECURSION

BASECASE1:
li $v0, 1
j RECURSION
BASECASE2:
li $v0, 2
RECURSION:

lw $ra, 4($sp) ############# RESTORE THE STACK
lw $a0, 0($sp)
addi $sp, $sp, 8
jr $ra