# Recursive factorial program.
# Version with as few registers as possible
# Written by NR Wagner, 23 Sep 1998
#
#    int fact(n)
#    {  if (n > 1) goto recur;
#       return n;
#   recur: return n * fact(n-1); }
#
#                   STACK
#                |              |                    |  Old
#                |--------------|                    |  Activation
#   old $sp ---> | Return addr  |                    |  Record
#             ===|==============|===          -------+
#   old -4  ---> | Return value |  <--- new +8       |
#                |--------------|                    |  New
#   old -8  ---> | Parameter n  |  <--- new +4       |  Activation
#                |--------------|                    |  Record
#   old -12 ---> | Return addr  |  <--- new $sp      |
#             ===|==============|===          -------+
#                | Return value |  <--- new -4       |
#                |--------------|                    |  Next (recursive)
#                | Parameter n  |                    |  Activation
#                |--------------|                    |  Record
#                | Return addr  |                    |
#             ===|==============|===         --------+
	.globl	main
main:	addu	$s7, $zero, $ra	# save return address

	li	$v0, 4			# print prompt
	la	$a0, prompt
	syscall
	li	$v0, 5			# read n
	syscall
	sw	$v0, -8($sp)		# n was in $v0
	jal	fact			# call fact
	lw	$a0, -4($sp)		# get return value off stack
	li	$v0, 1			# print return value = fact(n)
	syscall
	li	$v0, 4			# print newline
	la	$a0, newline
	syscall

	addu	$ra, $zero, $s7         # restore return address
	jr	$ra

	.globl	fact
fact:	addi	$sp, $sp, -12		# activation rec on stack
	sw	$ra, 0($sp)		# save return address on stack
	lw	$t1, 4($sp)		# $t1 = n
	li	$t2, 1			# $t2 = 1
	bgt	$t1, $t2, recur	        # goto recur if n > 1
	sw	$t1, 8($sp)		# put ret val (n) into stack
	b	endit			# same ending either way
recur: addi	$t3, $t1, -1		# $t3 = n - 1
	sw	$t3, -8($sp)		# put param n-1 into stack
	jal	fact			# call fact
	lw	$t4, -4($sp)		# $t4 = return value from stack
	lw	$t1, 4($sp)		# $t1 = n (call may have changed $t1)
	mul	$t5, $t1, $t4		# $t5 = $t1 * $t4 = n * fact(n-1)
	sw	$t5, 8($sp)		# store ret value into stack
endit: lw	$ra, 0($sp)		# restore ra from stack
	addi	$sp, $sp, 12		# pop activation record
	jr	$ra			# return

	.data
	.globl	prompt
prompt: .asciiz	"\nEnter n: "
	.globl	newline
newline: .asciiz	"\n"