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.


Need Your Help

T-SQL sum on decimal results in integer

sql tsql select decimal converter

Alright, T-SQL isn't acting as I would expect.