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

Question

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));
}

The condition could be if (n <= 1) to avoid one (useless) recursion. — Alexis Wilke
– Alexis Wilke, Commented Mar 10, 2014 at 8:36

Muhammad Safi · Accepted Answer · 2014-03-10 08:00:06Z

1

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.

answered Mar 10, 2014 at 8:00

Muhammad Safi

3832 gold badges6 silver badges16 bronze badges

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

Comments

Stack Player · Accepted Answer · 2014-03-10 20:22:11Z

0

"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.

answered Mar 10, 2014 at 20:22

Stack Player

1,4882 gold badges19 silver badges33 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related