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

As other answers noted, your function is not tail recursive, here is a tail recursive version of fibonacci:

long fibonacci(int n) {
    if (n == 0)
        return 0;
    else
        return fibonacciTail(n, 1, 0, 1);
}

long fibonacciTail(int n, int m, long fibPrev, long fibCurrent) {
    if (n == m)
        return fibCurrent;
    else
        return fibonacciTail(n, m + 1, fibCurrent, fibPrev + fibCurrent);
}

Also, the JVM does not do tail-call optimization so a stack frame will be allocated for every recursive call, making this quite an expensive operation. However it is important to note this is technically implementation dependent, see comments for link to IBM SDK that does TCO, and this SO question for more information.

An optimized version would be to do tail-call optimization manually, converting the above to a while loop with variable reassignment:

long fibonacciIter(int n) {
    int m = 1;
    long fibPrev = 0;
    long fibCurrent = 1;
    while (n != m) {
        m = m + 1;
        int current = fibCurrent;
        fibCurrent = fibPrev + fibCurrent;
        fibPrev = current;
    }
    return fibCurrent;
}

Answer 2

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.

Answer 3

In recursive version you are creating functions recursively which is expensive because function call involves pushing variables into stack, stack management, etc. while iteration operates on the same stack.

Answer 4

In the recursive code, the number of calls is proportional to the answer i.e. it is O(exp(n))

In the iterative method the run time is proportional to the number of times it loops. O(n)

To make matters worse, looping is a much faster operation than recursive calls so even if the orders where the same iterating there would still be significantly faster.

You can write the iterative fib like this.

public static long iterativeFib(int n) { // no chance of taking a long
    long a = 0, b = 1;    
    while(n-- > 0) {
        long c = a + b;
        a = b;
        b = c;
    }
    return c;
}

Does anyone have any ideas why this is running so slowly? Is it just a poorly written function?

Java is not a functional language and it doesn't do tail-call optimisation. This means that iteration is usually much faster than recursion in Java. (There are exceptions)