.data:
_msg1: .ascizz "fib("
_msg2: .ascizz ") = "
_msg3: .ascizz "\n"

.text:

_main:
; scanf("%d"), store in s0
li $v0, 5
syscall
move $s0, $v0
move $s0, $a0

addiu $sp, $sp, 4
sw $s0, 0($sp)
j _fib
lw $s0, 0($sp)
addi $sp, $sp, -4

move $s1, $v0
li $v0, 4
la $a0, _msg1
syscall

li $v0, 1
move $a0, $s0
syscall

li $v0, 4
la $a0, _msg2
syscall

li $v0, 1
move $a0, $s1
syscall

li $v0, 4
la $a0, _msg3
syscall

li $v0, 10
syscall

_fib:
addiu $sp, $sp, 4
sw $ra, 0($sp)

; if (n < 2) return n
li $t0, 2
cmp $a0, $t0
blt _end
; else return fib(n-1) + fib(n-2)

addi $a0, $a0, -1 ; n--
move $s0, $a0 ; store n

; get fib(n-1)
addiu $sp, $sp, 4
sw $s0, 0($sp)
addiu $sp, $sp, 4
sw $s1, 0($sp)
j _fib
lw $s1, 0($sp)
addi $sp, $sp, -4
lw $s0, 0($sp)
addi $sp, $sp, -4

; s1 = fib(n-1)
move $s1, $v0
; a0 = n-2
move $a0, $s0
addi $a0, $a0, -1

; get fib(n-2)
addiu $sp, $sp, 4
sw $s0, 0($sp)
addiu $sp, $sp, 4
sw $s1, 0($sp)
j _fib
lw $s1, 0($sp)
addi $sp, $sp, -4
lw $s0, 0($sp)
addi $sp, $sp, -4
;v0 = fib(n-2)
;v0 = fib(n-1) + fib(n-2)
add $v0, $v0, $s1

_end:
lw $ra, 0($sp)
addi $sp, $sp, -4
j $ra