# Implement a recursive factorial function.
#
# IF n = 1 THEN
#    RETURN 1
# ELSE
#    RETURN n * Fact(n-1)
# END

# $30 is the stack pointer.  Set up by CPU.
# $1 is used to return results from subprograms
# $2 Place Initial Argument here
# $3 Place the Result to here.
# $4 stores n-1 for the sub programs 
# $5 Scratch

.globl main

main:   addi    $30, $30, -4    # Space on stack for args
        addi    $2, $0, 5       # Put argument to _fact on the stack
        sw      $2, 0($30)

        jal     _fact           # call _fact
        addi    $30, $30, 4     # pop arg off stack

        llo     $3, n           # move the result (in $1) to n
        lhi     $3, n
        sw      $1, 0($3)

        trap    10              # halt

n:      .word   0               # should be 120 for 5!


_fact:  addi    $30, $30, -12   # allocate space on the stack
                                # for return address, etc.
        sw      $31, 8($30)     # save the return address
        sw      $3, 4($30)      # save registers we use
        sw      $4, 0($30)

        lw      $3, 12($30)     # get n
        addi    $5, $0, 1       # Set to 1 to test in next line
        beq     $3, $5, equal1  # test against 1
        bne     $3, $5, else_1  # Jump down two command, to "else_1" cannot put label name here, 
                                # relative jump
equal1: addi    $1, $0, 1       # n = 1, so return 1
        j       endif_1         # Jump to the label: endif_1

else_1: addi    $4, $3, -1      # n-1

        addi    $30, $30, -4    # allocate space on stack
        sw      $4, 0($30)      # push n-1 on the stack

        jal     _fact           # calc (n-1)!
        addi    $30, $30, 4     # pop arg off stack

        mult    $1, $3          # n * (n-1)!
        mfhi    $1              # place result in $1
        mflo    $1

endif_1:lw      $31, 8($30)     # Restore return address
        lw      $3, 4($30)      # Restore the saved registers
        lw      $4, 0($30)
        addi    $30, $30, 12    # Reset the stack

        jr $31                  # Return