Understanding recursion In MIPS

Question

I was reviewing a past assignment and was trying to follow the logic behind recursive functions. It simply passes the input to "fact," determines if >= 1, and passes it again to a loop. It is in loop that I become confused. I understand that when calling functions it is often wise to save the data using sw and loading it with lw when you are done. However, the loop calls to fact (which calls to the loop again) until input < 1. As you can see in the code below, it constantly saves the $ra and input in the same spot. Please notice that the lw code is not used until the recursion is actually done.

How does this not overwrite the old data? Is the old data merely pushed back? If so, how is popping only two items enough when the recursion is used many times? What is the purpose of $v0 in this code?

fact: slti $t0, $a0, 1 # test for n < 1, n is user input
      beq $t0, $zero, L1 # if n >= 1, go to L1
      li $v0, 1 # return 1
      jr $ra # return to instruction after jal

L1:   addi $sp, $sp, -8 # adjust stack for 2 items
      sw $ra, 4($sp) # save the return address
      sw $a0, 0($sp) # save the argument n
      addi $a0, $a0, -1 # n >= 1; argument gets (n – 1)
      jal fact # call fact with (n – 1)
      lw $a0, 0($sp) # return from jal: restore argument n
      lw $ra, 4($sp) # restore the return address
      addi $sp, $sp, 8 # adjust stack pointer to pop 2 items
      mul $v0, $a0, $v0 # return n * fact (n – 1)
      jr $ra # return to the caller

Answer 1

This is a classic example of stack manipulation.

Each time the function executes it grows the stack and stores $ra and $a0 at the newly allocated position.

You can see this by noting that $ra and $a0 are allocated relative to $sp (the stack pointer).

Each time the function executes the stack is expanded by subtracting 8 from $sp or enough room for two words. Likewise, when the function exits the stack is shrunk by adding 8 to $sp.

---

Think like this:

Suppose we want to calculate 5!.

The stack on each call to fact stores both $a0 and $ra. After 5 calls to fact the stack would look like this:

$a0: 5
$ra: back to main
----
$a0: 4
$ra: back to fact
---- 
$a0: 3
$ra: back to fact
----
$a0: 2
$ra: back to fact
----
$a0: 1
$ra: back to fact
----

Once the base-case executes ($a0 = 1) the stack begins to shrink. The $a0 = 1 stack returns 1 in $v0 and when we go to load $a0 we get 2 because we have already shrunk the stack. So we multiply 2 by 1 and then we return that value. The same process is repeated in the next stack-frame where we take the 2 returned in $v0 and multiply it by the 3 that we load from the stack and return 6 in $v0.

Hopefully from here you can see how:

addi $a0 $zero 5
jal fact

Would return 120 in $v0.