assembly - MIPS recursion: How to compute end result from stack -

my task implement egyptian multiplication in mips assembler recursively. think understood of relevant stuff, can't behind 1 thing: how end result computed? example in code(taken this question):

# int fact(int n) fact: subu    sp, sp, 32  # allocate 32-byte stack frame sw  ra, 20(sp)  # save return address sw  fp, 16(sp)  # save old frame pointer addiu   fp, sp, 28  # setup new frame pointer sw  a0,  0(fp)  # save argument (n) stack  lw  v0, 0(fp)   # load n v0 bgtz    v0, l2      # if n > 0 jump rest of function li  v0, 1       # n==1, return 1 j   l1      # jump frame clean-up code  l2: lw  v1, 0(fp)   # load n v1 subu    v0, v1, 1   # compute n-1 move    a0, v0      # move n-1 first argument jal fact        # recursive call  lw  v1, 0(fp)   # load n v1 mul v0, v0, v1  # compute fact(n-1) * n  #result in v0, clean stack , return l1: lw  ra, 20(sp)  # restore return address lw  fp, 16(sp)  # restore frame pointer addiu   sp, sp, 32  # pop stack jr  ra      # return .end    fact 

how/ when 2 lines between

jal fact 

and

l2 

ever reached? in understanding, either l1/l2 branched to, or fact called recursively...

---

/edit:

ok, seems figured out how implement recursively in mips. however, have 1 last problem: code below, program lacks 1 "turn", meaning last value isn't considered when computing final result.

pharao:     li $t0, 2       #load imm division 2     lw $a0, fac_1       #load fac_1 $a0     lw $a1, fac_2       #load fac_2 $a1     li $t7, 0       #zero $t7     li $t6, 1       #load 1 $t6      jal egypt       #jump egypt     j end     egypt:           subiu $sp,$sp,16    #space on stack 4 values     sw $ra,0($sp)       #store return address     sw $a0, 4($sp)      #store fac_1     sw $a1, 8($sp)      #store fac_2     divu $a1, $t0       #div fac_2 2     mflo $a1        #store quotient in $a1     mfhi $a2        #store remainder in $a2     sw $a2, 12($sp)     #store remainder on stack       multu $a0, $t0      #multiply fac_1 2     mflo $a0      beq $a1, $t6, return    #base case      jal egypt       #call egypt recursively  addingup:            lw $a0, 4($sp)      #load values stack     lw $a1, 8($sp)      #   "     lw $a2, 12($sp)     #   "      beqz $a2, return    #jump on if remainder 0      addu $t7, $t7, $a0  #add if remainder 1       return:           lw $ra, 0($sp)      #restore return address     addiu $sp, $sp, 16  #inc stackpointer     jr $ra 

when try running program values 10 , 20, result (in $t7) 40, because last value, 160, isn't added. how can fix this?

thanks!

jal instruction jump , link, means stores next instruction's address in r31 , jumps label given. it's (one/the) way subroutine calls in mips assembler.

the jr $ra jumps address contained in r31, means returns instruction following jal. can see, that's done before .end.

in short, jal subroutine call, , when call returns, execute instructions following jal.

in edited question, check base case bit strangely, like;

a = n >> 1; b = n & 1; if(a == 0)    return 0; ...do calculation... 

...when better base case be;

if(n == 0)    return 0; = n >> 1; b = n & 1; ...do calculation... 

the problem first base case b can still 1 , give result, return anyway without using value.