CODEWITHSUNDEEP
assemblyrecursionmips
rigon
rigon

Reputation: 1410

Recursion in MIPS

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

Here's the implementation in C:

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

Upvotes: 4

Views: 29291

Answers (4)

D&#39;Nabre
D&#39;Nabre

Reputation: 2262

Here is the code to do a recursive factorial function in MIPS assembly. Changing it to do Fibonacci is left as an exercise to the reader. (Note: delay slots aren't optimized in this code, as it's 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

Upvotes: 9

Tom
Tom

Reputation: 45104

-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.

Upvotes: 4

Ofir
Ofir

Reputation: 8362

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.

Upvotes: 1

integer
integer

Reputation: 1075

Compile your C function to an object file and look at

objdump -d fib.o

Could be your starting point.

Upvotes: 0

Related Questions