0

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
Improve this question

1 Answer 1

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Thats' what it looked like to me at first, but jal fact is used before lw or addi $sp, $sp, 8 are called. Wouldn't this cause what's on the stack to be overwritten?
No. jal is just a jump that also puts the current PC into $ra. If the function is to be executed 8 times it will first expand 8 times, and then it will shrink 8 times.
Ok, then what about mul $v0, $a0, $v0 ? Because that comes after the jal and lws, wouldnt that mean that we are just multiplying n by 1?
The value of $a0 is reloaded before the mul statement. The value of $v0 is dictated by the call to fact.
Can you give me an example of how this would work? For instance, say the number we are passing is 5. What would happen step by step?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.