.data

.text
main:
    li      $v0,            5                       # read in
    syscall 
    move    $s0,            $v0                     # s0 is the n
    move    $a0,            $s0                     # set the first call arg as n
    jal     hanoi                                   # call proc
    move    $a0,            $v0                     # print out
    li      $v0,            1
    syscall 
    li      $a0,            0
    li      $v0,            17
    syscall 

hanoi:
    li      $t0,            1
    ble     $a0,            $t0,    hanoi_bottom    # if n <= 1, return
    j       hanoi_recur
hanoi_bottom:
    li      $v0,            1                       # return 1
    jr      $ra
hanoi_recur:
    subi    $sp,            $sp,    8               # move sp down by 2 word
    sw      $s0,            4($sp)                  # first word is the n in caller
    sw      $ra,            0($sp)                  # second word is the return addr of this callee
    move    $s0,            $a0
    subi    $a0,            $s0,    1
    jal     hanoi
    sll     $v0,            $v0,    1               # hanoi(n - 1) * 2
    ori     $v0,            $v0,    1               # hanoi(n - 1) * 2 + 1
    lw      $s0,            4($sp)                  # reverse s0
    lw      $ra,            0($sp)                  # reverse ra
    addi    $sp,            $sp,    8
    jr      $ra