# Computes the factorial of an integer recursively.

.data
    prompt:    .asciiz   "Enter n: "
    leading_output:    .asciiz   "n! is "

.text
main:
    # Prompt for the user to enter n
    li $v0, 4
    la $a0, prompt
    syscall

    # Read n from standard in
    li $v0, 5
    syscall

    # Call the factorial function with the integer that was read
    move $a0, $v0
    jal factorial

    # Store the factorial result in $t0
    move $t0, $v0

    # Print the leading output string
    li $v0, 4
    la $a0, leading_output
    syscall

    # Print the factorial
    li $v0, 1
    move $a0, $t0
    syscall
	
	  # Print a newline
	  li $v0, 11
    li $a0, '\n'
	  syscall

	  # exit
    li $v0, 10
    syscall

	
# Computes n! recursively
# Parameters:
#   $a0: n
# Return values:
#   $v0: n!
factorial:
    # Base case is 0!, in which case we jump to the base_case label
    beq $a0, 0, factorial_base_case

    # We need to save $ra and $a0 on the stack. Each is 4 bytes, so the stack
    # pointer needs to be decremented by 8. Since 8 is a multiple of 8, there
    # is no need to add padding.
    addi $sp, $sp, -8

    # Now we can store the needed registers on the stack. Referencing the stack
    # requires an offset from $sp, which is the address of the word on the top
    # of the stack. X($y) refers to the address X bytes away from $y.
    sw $ra, 4($sp)
    sw $a0, 0($sp)

    # Decrement $a0 to pass to the recursive call
    addi $a0, $a0, -1

    jal factorial

    # Now $v0 will contain (n - 1)! which we need to multiply by n, which we
    # stored on the stack
    lw $t0, 0($sp)
    mult $t0, $v0

    # The result is in LO. We need to return the result, so copy it to $v0
    mflo $v0

    # Restore $ra from the stack
    lw $ra, 4($sp)

    # Pop the top two words off the stack
    addi $sp, $sp, 8

    # At last we can return!
    jr $ra

factorial_base_case:
    # We get here if n is 0. 0! is 1, so all we need to do is set $v0 to 1 and
    # return
    li $v0, 1
    jr $ra
