# Not understanding instruction execution order in recursive factorial function (MIPS)

I am confused about how this code multiplies n for each n-1 given the order of the sequences. Let me explain how I see what is happening and you can point out where I'm wrong.

If n is less than 0, the comparison is false and the program simply returns 1(if this is the first time it has been called). If not, L1 is called and it gets decremented. Here is where I get confused. It looks like fact is being called again immediately after the decrement and the multiplication function never takes place. In this case, if n = 5, then it would simply decrement until n = 0 and finally multiply 1 x 5 at the very end.

My best guess is that I'm missing something in terms of it pushing/popping the values on and off the stack, but I haven't a clue.

fact: 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 slti $t0, $a0, 1 # test for n < 1 beq $t0, $zero, L1 # if n >= 1, go to L1 addi $v0, $zero, 1 # return 1 addi $sp, $sp, 8 # pop 2 items off stack jr $ra # return to instruction after jal L1: 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

Edit:

Here is the function in C that is to be taking place here:

int fact (int n) { if (n < 1) return (1); else return (n * fact(n – 1)); }

## Answers

Lets say you want 3!. So to start of n = 3.

n < 1 not true

--> return 3 * fact(2)

Back into function with n = 2

n < 1 not true

-> return 2* fact(1)

Back into function with n = 1

again n<1 not true

-> return 1* fact(0)

Back into function with n = 0

now n<1 true

return 1

Recursions starts to unwind

1 replaces fact(0) and function returns 1*1

1 replaces fact(1) in and function returns 2*fact(1) which is 2

2 replaces fact(2) and function returns 3*fact(2) which is 6

Recursion ends.

"My best guess is that I'm missing something in terms of it pushing/popping the values on and off the stack, but I haven't a clue."

This is exactly it;

You are forgetting to pop out of the stack, once you call down to 4 then 3 then 2 then 1 (here gets the value 1), you return AT $ra ! and the function continues and does the multiplication one by one then popping each stack level one by one till the final $ra which ends the entire function call.