# MIPS recursion: How to compute end result from stack

My task is to implement egyptian multiplication in MIPS assembler recursively. I think I understood most of the relevant stuff, but I just can't get behind one thing: How is the end result computed? For example in this code(taken from this question):

```# int fact(int n)
fact:
subu    sp, sp, 32  # Allocate a 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) to stack

lw  v0, 0(fp)   # Load n into v0
bgtz    v0, L2      # if n > 0 jump to rest of the function
li  v0, 1       # n==1, return 1

L2:
lw  v1, 0(fp)   # Load n into v1
subu    v0, v1, 1   # Compute n-1
move    a0, v0      # Move n-1 into first argument
jal fact        # Recursive call

lw  v1, 0(fp)   # Load n into v1
mul v0, v0, v1  # Compute fact(n-1) * n

#Result is in v0, so clean up the stack and 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 are the two lines between

```jal fact
```

and

```L2
```

ever reached? In my understanding, either L1/L2 are branched to, or fact is called recursively...

/Edit:

Ok, it seems that I figured out how to implement something recursively in MIPS. However, I have one last problem: With the code below, my program lacks one "turn", meaning that the last value isn't considered when computing the final result.

```pharao:
li \$t0, 2       #load imm for division by 2
lw \$a0, fac_1       #load fac_1 into \$a0
lw \$a1, fac_2       #load fac_2 into \$a1
li \$t7, 0       #zero \$t7
li \$t6, 1       #load 1 into \$t6

j end

egypt:
subiu \$sp,\$sp,16    #space on stack for 4 values
sw \$a0, 4(\$sp)      #store fac_1
sw \$a1, 8(\$sp)      #store fac_2
divu \$a1, \$t0       #div fac_2 by 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 by 2
mflo \$a0

beq \$a1, \$t6, return    #base case

jal egypt       #call egypt recursively

lw \$a0, 4(\$sp)      #load values from stack
lw \$a1, 8(\$sp)      #   "
lw \$a2, 12(\$sp)     #   "

beqz \$a2, return    #jump on if remainder is 0

return:

lw \$ra, 0(\$sp)      #restore return address
addiu \$sp, \$sp, 16  #inc stackpointer
jr \$ra
```

When I try running the program with the values 10 and 20, the result (in \$t7) is 40, because the last value, 160, isn't added. How can I fix this?

Thanks!

jal is the instruction JUMP AND LINK, which means it stores the next instruction's address in r31 and jumps to the label given. You could say it's (one/the) way to do subroutine calls in MIPS assembler.

The jr \$ra jumps to the address contained in r31, which means it returns to the instruction following jal. As you can see, that's done just before the .end.

In short, jal is a subroutine call, and when the call returns, it will execute the instructions following jal.

In your edited question, you check the base case a bit strangely, something like;

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

...when a much better base case would be;

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

The problem with the first base case is that b can still be 1 and give a result, but you return anyway without using the value.