Why does this recursive fibonacci function run so poorly?

Question

If I run the following code:

public static void main(String[] argsv) {

    long whichFib = 45;
    long st;
    st = System.currentTimeMillis();
    System.out.println(recursiveFib(whichFib));
    System.out.println("Recursive version took " + (System.currentTimeMillis() - st) + " milliseconds.");

    st = System.currentTimeMillis();
    System.out.println(iterativeFib(whichFib));
    System.out.println("Iterative version took " + (System.currentTimeMillis() - st) + " milliseconds.");

}

public static long recursiveFib(long n) {

    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;

    return recFib(n - 1) + recFib(n - 2);
}

public static long iterativeFib(long n) {

    if (n == 0)
        return 0;
    else if (n == 1 || n == 2)
        return 1;

    long sum = 1;
    long p = 1;
    long u = 1;

    for (int i = 2; i < n; i++) {
        sum = p + u;
        p = u;
        u = sum;
    }

    return sum;
}

I get the following output:

1134903170 Recursive version took 5803 milliseconds. 1134903170 Iterative version took 0 milliseconds.

I feel like I have done something incorrect here. I thought that the tail call (the final line in the recursive fibonacci method) would be optimised by the compiler, bringing it closer in speed to the iterative version. Does anyone have any ideas why this is running so slowly? Is it just a poorly written function?

N.B. I am using Oracle JDK 1.7

Answer 1

return recFib(n - 1) + recFib(n - 2);

Since you are making two recursive calls, not one, it is unlikely that the compiler is able to do the traditional tail call optimization.

You could check this page for ideas on how to write recursive Fibonacci solver with tail call optimization.