Recursive function using MIPS assembly

Question

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?

Thanks in advance

Answer 1

Here is the code for your function. I know you are not looking for the answer but sometime looking for an example and how it works get's your more easy at the point you understand how it really worked.

.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. Hope i helped you out and good luck getting a better grasp with MIPS programming!