.text

main:
    li      s1, 2
    li      s2, 1
    li      s3, 11

loop:
    mv      a2, s2
    call    fib

    mv      a1, a0   # move return value for printing
    li      a0, 1    # print integer
    ecall

    li      a1, ' '
    li      a0, 11   # print char
    ecall

    addi    s2, s2, 1
    bge     s2, s3, exit
    j       loop

exit:
    # exit the program
    li      a0, 10
    ecall

fib:
    bge     a2, s1, fib_recurse
    # base case
    mv      a0, a2
    jr      ra

fib_recurse:
    addi    sp, sp, -12  # 12 bytes needed for stack
    sw      ra, 0(sp)    # save return address

    sw      a2, 4(sp)    # save n
    addi    a2, a2, -1   # n -= 1
    jal     fib
    lw      a2, 4(sp)    # restore n
    sw      a0, 8(sp)    # save return value from fib(n-1)

    addi    a2, a2, -2   # n -= 2
    jal     fib

    lw      t3, 8(sp)    #  restore return value from fib(n-1)
    add     a0, a0, t3   # actual return value

    lw      ra, 0(sp)    # restore ra
    addi    sp, sp, 12   # tear down the stack
    jr      ra