C Code

    #include <stdio.h>

    int fib(int n);

    int main()
    {
        printf("Fibonacci(4): %d\n",
               fib(4));
    }

    int fib(n)
    {
        int result1, result2;
        int finalResult;

        if ( n < 3 )
            return 1;

        result1 = fib(n-1);
        result2 = fib(n-2);
        finalResult = result1 + result2;
        return finalResult;
    }

Diagram

MIPS Code

    ----------------------------------------------------------------------
    main:       ...                     # stuff not shown
                addi $a0, $zero, 4      # $a0 = n = 4
                jal fib                 # call fib(n); result is in $v0
                ...                     # stuff not shown to print & exit
    ----------------------------------------------------------------------
    # The "fib" and "ELSE" labels are required; the others are to aid
    # understanding.
    # Note: As always, $a0 holds 1st parameter: n
    fib:        slti $t0, $a0, 3        # TEST BASE CASE: t0 = 1 if n < 3
                beq $t0, $zero, ELSE    # goto ELSE if n >= 3
                addi $v0, $zero, 1      # put return value (1) in $v0
                jr $ra                  # return
    ELSE:       addi $sp, $sp, -12      # PUSH: adjust stack ptr for 3 items
                sw $ra, 0($sp)          # store $ra on stack
                sw $s0, 4($sp)          # store $s0 on stack
                sw $s1, 8($sp)          # store $s1 on stack
                add $s0, $a0, $zero     # save n ($a0) in $s0
    FirstRecCall:
                addi $a0, $s0, -1       # put n-1 in $a0
                jal fib                 # recursive call; result will be in $v0
    WeAreBack1: add $s1, $s1, $v0       # save result1 ($v0) in $s1
    SecndRecCall:
                addi $a0, $s0, -2       # put n-2 in $a0
                jal fib                 # recursive call; result will be in $v0
    WeAreBack2: add $v0, $s1, $v0       # save result1 + result2 in $v0
    PopFrmStk:  lw $s1, 8($sp)          # POP: retrieve $s1 from stack
                lw $s0, 4($sp)          # retrieve $s0 from stack
                lw $ra, 0($sp)          # retrieve $ra from stack
                addi $sp, $sp, 12       # restore stack pointer
    Return:     jr $ra                  # return
    # Note: As always, $v0 holds result to be returned
    ----------------------------------------------------------------------