CODEWITHSUNDEEP
assemblyrecursionmips
lucian_x098
lucian_x098

Reputation: 35

mips assembly: understanding recursion

so I have this code which computes the factorial (in general) but in this example it computes the factorial of 10

    .data 0x10008000
    .word 10
    .word 1
    .word 0
    .ascii "The factorial of 10 is %d \n"
    .text
    .globl main
main:
    addi $sp, $sp, -32
    sw $ra, 20($sp)
    sw $fp, 16($sp)
    addiu $fp, $sp,28
    lw $a0, 0($gp)
    jal fact

    ...

    lw $ra, 20($sp)
    lw $fp, 16($sp)
    addiu $sp, $sp, 32
    jr $ra
fact:
    addiu $sp, $sp, -32
    sw $ra, 20($sp)
    sw $fp, 16($sp)
    addiu $fp, $sp, 28
    sw $a0, 0($fp)
    lw $v0, 0($fp)      
    lw $t0, 4($gp)
    slt $t1,$v0,$t0     
    bne $t0, $t1, L2    
    addi $v0, $v0, 1
    jr L1
 L2:
    lw $v1, 0($fp)
    addi $v0, $v1, -1
    sw $v0, 8($gp)
    lw $a0, 8($gp)
    jal fact                   
    lw $v1, 0($fp)      
    mul $v0, $v0, $v1    
 L1:
    lw $ra, 20($sp)
    lw $fp, 16($sp)
    addiu $sp, $sp, 32
    jr $ra

my problem is this don't Ι need a jr L1 command after the multiplication in L2? How does the recursion works? Doesn't it need some way to store the previous numbers? I think this is the job of the stack but it seems to me that every time the function is called the previous stored variables ars overwritten.

ps I don't know if anyone understood my problem I'm sorry for my poor english...

Upvotes: 1

Views: 1203

Answers (2)

Michael
Michael

Reputation: 58427

The way your fact function works is like this:

int fact(unsigned int n) {
  if (n < 1) {
    return n+1;
  } else {
    return fact(n-1) * n;
  }
}

As you can see it recursively calls itself until the argument becomes < 1, at which point it returns 1 (i.e. 0+1) and goes back up the call chain to perform the multiplications.

For example, if you did fact(3);, the call chain would look like this:

fact(3): fact(2) * 3
  fact(2): fact(1) * 2
    fact(1): fact(0) * 1
      fact(0): 1
      1
    * 1 (==1)
  * 2 (==2)
* 3 (==6)

The value of the function is returned in $v0. To get the current value of n for performing the multiplication fact(n-1) * n, the function stores it on the current stack frame (sw $a0, 0($fp)) and reads it back right before the multiplication (lw $v1, 0($fp)).
As Michael Burr commented, a new stack frame is created upon each entry of fact. That's what the first 4 instructions of fact do (reserve some space on the stack, save the current frame pointer and return address, and point the frame pointer to the new stack frame).

There's no need to jump to L1 after the multiplication since L1 immediately follows it (i.e. the label will be reached anyway).

Upvotes: 2

ady
ady

Reputation: 173

recursion requires the introduction of "manual stack management" which apparently takes some effort to implement. Not all compilers support it for various reasons

It all happens on the stack which expands and contracts between different parameter trees and is quite an amazing thing to observe

If you want to "learn about that stuff" I suggest you do some research on the "towers of hanoi" which is a highly recursive real world problem

There's a nice explanation here

http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html

Once you understand recursion it can be used for quite complicated problems, like sudoku solvers

A typical sudoku has around 20 to 30 different scenarios

So programming for 20+ manual scenarios can be circumvented by producing a single recursive solution which also magically works for "impossible" sudokos

Upvotes: 0

Related Questions