assembly - Not understanding instruction execution order in recursive factorial function (MIPS) -
i confused how code multiplies n each n-1 given order of sequences. let me explain how see happening , can point out i'm wrong.
if n less 0, comparison false , program returns 1(if first time has been called). if not, l1 called , gets decremented. here confused. looks fact being called again after decrement , multiplication function never takes place. in case, if n = 5, decrement until n = 0 , multiply 1 x 5 @ end.
my best guess i'm missing in terms of pushing/popping values on , off stack, haven't clue.
fact: addi $sp, $sp, -8 # adjust stack 2 items sw $ra, 4($sp) # save return address sw $a0, 0($sp) # save argument n slti $t0, $a0, 1 # test n < 1 beq $t0, $zero, l1 # if n >= 1, go l1 addi $v0, $zero, 1 # return 1 addi $sp, $sp, 8 # pop 2 items off stack jr $ra # return instruction after jal l1: addi $a0, $a0, -1 # n >= 1; argument gets (n – 1) jal fact # call fact (n – 1) lw $a0, 0($sp) # return jal: restore argument n lw $ra, 4($sp) # restore return address addi $sp, $sp, 8 # adjust stack pointer pop 2 items mul $v0, $a0, $v0 # return n * fact (n – 1) jr $ra # return caller
edit:
here function in c taking place here:
int fact (int n) { if (n < 1) return (1); else return (n * fact(n – 1)); }
lets want 3!. start of n = 3.
n < 1 not true
--> return 3 * fact(2)
back function n = 2
n < 1 not true
-> return 2* fact(1)
back function n = 1
again n<1 not true
-> return 1* fact(0)
back function n = 0
now n<1 true
return 1
recursions starts unwind
1 replaces fact(0) , function returns 1*1
1 replaces fact(1) in , function returns 2*fact(1) 2
2 replaces fact(2) , function returns 3*fact(2) 6
recursion ends.
Comments
Post a Comment