Recursive function using MIPS assembly

I'm having some trouble on an assignment and would appreciate some help. I'm not asking for the answer, I prefer to put two and two together to figure it out myself, but I know so little about MIPS its hard for me to know where to start.

Here is what I started with

.data .text main: addi $sp, $sp, -16 #prepare stack for 4 items sw $s0, 0($sp) sw $s1, 4($sp) sw $s2, 8($sp) sw $ra, 12($sp) move $s0, $a0 move $s1, $a1 add $s2, $s0, $s1 #add two previous numbers and store result in $s2 move $v0, $s2 #put answer into $v0 lw $s0, 0($sp) lw $s1, 4($sp) lw $s2, 8($sp) lw $ra, 12($sp) addi $sp, $sp, 16 jr$ra 

Essentially we are to use a recursive function to calculate the fibonacci numbers and a loop to print out the first 10 numbers of the fibonacci sequence.

I have looked up many examples but they all use instructions that we haven't learned yet so I can't make sense of it and I can only assume we aren't expected to use them. In the code above I'm essentially creating a stack to store the $ra along with three values, the two numbers to be added and the sum. Part of my problem is understanding where the function starts and ends and what the totality of the work being done is.

We were also given that to print you use the following

li $v0, 1 move $a0, $s0 syscall 

Am I correct in thinking this is printing the value stored in $v0?

4 Answers

Here is the code for your function. I know you are not looking for the answer but sometimes looking for an example and seeing how it works gets you more easily to the point where you understand how it really works.

.data msg1: .asciiz "Give a number: " .text .globl main main: li $v0, 4 la $a0, msg1 syscall # print msg li $v0, 5 syscall # read an int add $a0, $v0, $zero # move to $a0 jal fib # call fib add $a0, $v0, $zero li $v0, 1 syscall li $v0, 10 syscall fib: # $a0 = y # if (y == 0) return 0; # if (y == 1) return 1; # return fib(y - 1) + fib(y - 2); #save in stack addi $sp, $sp, -12 sw $ra, 0($sp) sw $s0, 4($sp) sw $s1, 8($sp) add $s0, $a0, $zero addi $t1, $zero, 1 beq $s0, $zero, return0 beq $s0, $t1, return1 addi $a0, $s0, -1 jal fib add $s1, $zero, $v0 # $s1 = fib(y - 1) addi $a0, $s0, -2 jal fib # $v0 = fib(n - 2) add $v0, $v0, $s1 # $v0 = fib(n - 2) + $s1 exitfib: lw $ra, 0($sp) # read registers from stack lw $s0, 4($sp) lw $s1, 8($sp) addi $sp, $sp, 12 # bring back stack pointer jr $ra return1: li $v0,1 j exitfib return0: li $v0,0 j exitfib 

Like Gusbro said in order to use recursion in mips you will have to do 2 things. jal (jump and link) to the name of the function but first always store the return address into a stack, $ra, so in the future if you want to return back to the beginning you will be able to using jr $ra. If you don't save a return address and try to access it via jr you will most likely get an invalid program counter error.

Here goes some hints:

You have to write a recursive function, but you are not writing a function at all. To write this function in MIPS assembler I suggest you first write it in a higher level language (C). So it would go something like this:

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

The first line checks whether you are in a base case of the recursion (n=0 or n=1). If thats the case, fib(n) returns n. Otherwise the recursion step goes which returns the sum of fib(n-1) plus fib(n-2).

So you will have to write a function, define the input/output parameters (which register will held n and which will return fib(n). The manually compile the C code. To start a function, just add a label

fib: 

• then put your stack management code there.
• then translate the IF-THEN-ELSE to MIPS assemble.
• to issue the recursive call, use jal instruction.
• Before returning from the function with jr $ra restore the saved values from the stack.
• Your main program will load the input parameter (the register used for input argument n), then jal fib.

This explains how to implement the Fibonacci function in MIPS as well as how to translate a MIPS function back to equivalent C code, it's well detailed : Fibonacci function in MIPS by illinois.edu

1. The code for the base case:

fib: bgt $a0, 1, recurse move $v0, $a0 jr $ra 

2. Convert the code for the base case.

fib: bgt $a0, 1, recurse move $v0, $a0 jr $ra 

3. Save callee- and caller-saved registers on the stack. recurse:

sub $sp, $sp, 12 # We need to store 3 registers to stack sw $ra, 0($sp) # $ra is the first register sw $a0, 4($sp) # $a0 is the second register, we cannot assume $a registers will not be overwritten by callee 

4. Call fib recursively:

addi $a0, $a0, -1 # N-1 jal fib sw $v0, 8($sp) # store $v0, the third register to be stored on the stack so it doesn’t get overwritten by callee 

5. Call fib recursively again:

 lw $a0, 4($sp) # retrieve original value of N addi $a0, $a0, -2 #N-2 jal fib 

Write a recursive version of 𝑟add() in C or C++, then use this program to develop a MIPS program that gets as input two integers 0<𝑎 ≤255, and 0<𝑏 ≤255, and returns the result of 𝑟add(𝑎,𝑏) in $v1.