Recursion in MIPS

Question

I want implement a recursive program in assembly for MIPS, more specifically the well known Fibonacci function.

There's the implementation in C:

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

Answer 1

Post your attempt and we'll try and help.

Recursion and micro's don't always play well together though...

Answer 2

Compile your C function to an object file and look at

objdump -d fib.o

Could be your starting point.

Answer 3

Hint - think about a stack.

By the way, recursion is a really bad solution to the problem in terms of complexity (both time and space). A loop and two variables would work much better.

Answer 4

-Load n-1 into $a0

-Use a jal instruction to call fib recursively.

-Fetch result from the $v0 register.

-Load n-2 into $a0

-Use a jal instruction to call fib recursively.

-Fetch result from the $v0 register.

Then, there's something with the addu instruction...

Oh yeah, you must check the if using a branch, but that has nothing to do with recursion.

if you need help, the compiler is your friend.

$gcc -c -g fib.c

$objdump -S fib.o

but

$gcc -S -mrnames fib.c -o fib.s

will be clearer.

Answer 5

Where is the full assembly to do a recursive factorial function in MIPS assembly, changing it to do fib is left as an exercise to the reader. (Not delay slots aren't optimized in this code, it designed for readability).

# 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
    j   L1      # jump to frame clean-up code

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