[MIPS] Recursion Example - Fibonacci

In MIPS, we can implement recursive functions using stack. The stack is necessary to keep track of values in between calls. Let's try implementing the Fibonacci function. 

Pseudocode in C:

int fib (int n) {
	if (n <= 1)
		return n;
	else 
		return fib(n-1) + fib(n-2);
}

Code in MIPS Assembly: 

We will learn how to write a recursive function in MIPS assembly language using two approaches: an intuitive approach and the standard approach. For the intuitive approach, we will be saving variables in stacks before every call that would overwrite them, unlike in the standard approach where `$s` registers are used to back up the variables. 

 

First, check for the base case. Typically, the argument `n` corresponds to argument register `$a0`, and the return value is passed onto value register `$v0`. 

fib:
	#if (n<=1), branch to fib_end
	ble $a0, 1, fib_end 

	#else, return fib(n-1) + fib(n-2)
	#...
fib_end: 
	#return n
	addi $v0, $a0, 0

Now, how do we implement the rest of the function? Take a look at the visual representation of how recursive calls are made in the Fibonacci sequence. 

Recursion Tree for Computing 5th Number of Fibonacci Sequence

In order to be able to return to a caller function from its callee, we must save the return address `$ra` before the callee makes a call to another procedure.

 

For example, say `fib(4)` makes a call to `fib(2)`. We want to be able to return to `fib(4)` after we are done with computing `fib(2)`. However, if `fib(2)` makes a call to another procedure -- `fib(1)` -- the return address will be overwritten and we won't be able to return to the exact line where `fib(2)` was called in `fib(4)`. 

 

This is not necesary if the callee is a leaf procedure. If `fib(3)` makes a call to `fib(1)`, we don't need to save the return address since `$ra` will not be overwritten by performing another recursion. 

 

Hence, for `fib(n)`, push `$ra` into stack before calling `fib(n-1)`. This way, we can pop `$ra` from the stack to return to the caller.  

fib:
	#if (n<=1), branch to fib_end
	ble $a0, 1, fib_end 

	#else, push $ra
	addi $sp, $sp, -4
	sw $ra, 0($sp) 
    
	#call fib(n-1)
	addi $a0, $a0, -1
	jal fib #$ra = addressA
 
	#call fib(n-2)
	addi $a0, $a0, -2    
	jal fib #$ra = addressB  

	#return value = fib(n-1) + fib(n-2)
	#...

	#pop $ra 
	lw $ra, 0($sp)      
	addi $sp, $sp, 4   

	#back to caller
	jr $ra 
      
fib_end: 
	#return n
	addi $v0, $a0, 0 

	#continue from addressA or addressB
	jr $ra

Aside from the return address, what other values should we have backed up for later use?

 

Before making a recursive call, we have to back up EVERY variable whose original value has to be retrieved for use after the call. This usually includes the parameter variable. It is not necessary to save a value that remains unchanged during the call or is not used after the call. 

 

After `fib(n)` calls `fib(n-1)`, it calls `fib(n-2)`. Since `fib(n-1)` may overwrite the value of n, which we need to make a call to `fib(n-2)`, the value of n needs to be backed up. Therefore, push `n` into stack before calling `fib(n-1)` and pop `n` after calling `fib(n-1)`.

 

In addition, when the value of `fib(n-2)` is returned, we need to retrieve the return value of `fib(n-1)` for computing `fib(n-1) + fib(n-2)`. so push `fib(n-1)` into stack before calling `fib(n-2)` and pop it after the execution of `fib(n-2)`. 

 

The corresponding code is down below: 

main: 
	li $a0, 5
	jal fib
				
	move $a0, $v0
	li $v0, 1
	syscall
	
	li $v0, 10
	syscall
	
fib:
	#if (n<=1), branch to fib_end
	ble $a0, 1, fib_end 

	#push n and $ra 
	addi $sp, $sp, -8
	sw $a0, 0($sp)
	sw $ra, 4($sp) 
   
	#call fib(n-1)
	addi $a0, $a0, -1
	jal fib
 
	#pop n
	lw $a0, 0($sp)
    
	#push fib(n-1)
	sw $v0, 0($sp) 

	#call fib(n-2)
	addi $a0, $a0, -2    
	jal fib  
    
	#pop fib(n-1) and $ra 
	lw $t0, 0($sp) 
	lw $ra, 4($sp)      
	addi $sp, $sp, 8    

	#return fib(n-1) + fib(n-2)
	add $v0, $v0, $t0
	jr $ra
      
fib_end: 
	#return n
	addi $v0, $a0, 0 
    
	jr $ra

Following MIPS Calling Convention

In the above code, we are backing up values as a caller before making a call to the callee. Since a recursive function is both a caller and a callee at the same time, this approach isn't wrong -- but to follow the MIPS calling convention, using `$s` registers for values that need to be preserved would be more correct. When using `$s`, you can simply push and pop all `$s` values at the beginning and the end of a callee function

• check this blog post https://abcdefshin.tistory.com/9 on MIPS registers if you are unfamiliar with the concept 

Since we need to use `$a` registers for arguments, we will use both `$a0` and `$s0` to denote `n`. The difference is that when you call `fib(n-1)` and `fib(n-2)`, `$a0` will be set to `n-1` or `n-2`, but `$s0` will remain as `n` throughout the procedure once you set it to `n`. Take a look at the steps below for better understanding. 

• `\underline{fib(5)}`: `$a0 = 5`
  • save `$s0 = ?` (not important, this value won't be used) 
  • set `$s0 = 5` 
  • `$a0 = $s0 - 1 = 4`
  • call `\underline{fib(4)}`:
    • save `$s0 = 5`
    • set `$s0 = 4`
    • `$a0 = $s0 - 1 = 3`
    • call `\underline{fib(3)}`:
      • save `$s0 = 4`
      • set `$s0 = 3`
      • `$a0 = 2`
      • ...
      • restore `$s0 = 4`
    • `$a0 = $s0 - 2 = 2`
    • call `\underline{fib(2)}`:
      • save `$s0 = 4`
      • set `$s0 = 2`
      • ...
      • restore `$s0 = 4`
    • restore `$s0 = 5`
  • `$a0 = $s0 - 2 = 3`
  • call `\underline{fib(3)}`: ...

Now, we can revise our implementation of the Fibonacci function to use the correct registers: 

main: 
    li $a0, 5
    jal fib
				
    move $a0, $v0
    li $v0, 1
    syscall
	
    li $v0, 10
    syscall
	
fib:
    #if (n<=1), branch to fib_end
    ble $a0, 1, fib_end 
    
    #save all the $s values and $ra 
    addi $sp, $sp, -12
    sw $s0, 0($sp)
    sw $s1, 4($sp) 
    sw $ra, 8($sp)

    #for n to be saved, put it in $s0
    move $s0, $a0 

    #call fib(n-1)
    addi $a0, $s0, -1
    jal fib
    
    #for fib(n-1) to be saved, put it in $s1
    move $s1, $v0

    #call fib(n-2)
    addi $a0, $s0, -2    
    jal fib  

    #result = fib(n-1) + fib(n-2)
    add $v0, $v0, $s1

    #restore $s values and $ra before returning to caller
    lw $s0, 0($sp) 
    lw $s1, 4($sp)
    lw $ra, 8($sp)      
    addi $sp, $sp, 12

    jr $ra
      
fib_end: 
    #return n
    addi $v0, $a0, 0 
    
    jr $ra