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

Your `recursiveFib` is not tail recursive as the `+` happens after the recursive calls. In fact it will be O(2^n) (as each call generates two recursive calls which in turn generate two calls each etc) vs the O(n) of the iterative version. — Ian Roberts, Jan 12 '13 at 15:12
There is 2.2 billion function calls, whereas with iterative you do 40~ iterations — Esailija, Jan 12 '13 at 15:13

Johan Kotlinski · Answer 1 · 2013-01-12T15:16:57.700

6

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.

edited Jan 12 '13 at 15:16

answered Jan 12 '13 at 15:11

Johan Kotlinski

25,185
9
78
101

I see. How would one make a more optimised recursive fib function in Java? – eggonlegs Jan 12 '13 at 15:12
"Since you are making two recursive calls..." The point is that the **last** operation is not a recursive call. The last operation is the addition of the two results, so it is not tail recursive. – michael.kebe Sep 20 '13 at 09:16

score 5 · Accepted Answer · edited May 23 '17 at 11:58

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;
}

It seems like IBM Java SDK does tail-call optimization (taken from comment on some old post, with the link updated): http://publib.boulder.ibm.com/infocenter/javasdk/v5r0/topic/com.ibm.java.doc.diagnostics.50/diag/understanding/jit_optimize_inline.html — nhahtdh, Jan 12 '13 at 15:23
@nhahtdh Good catch, I updated my post to reflect that this, thanks for posting a link! — Alex DiCarlo, Jan 12 '13 at 15:25

score 1 · Answer 3 · answered Jan 12 '13 at 15:11

1

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.

answered Jan 12 '13 at 15:11

hmatar

2,437
2
17
27

This is not a good explanation in case of Java, since it runs on JVM, and the JVM (by theory) can do tail-call optimization that may make a recursive code runs iteratively. Whether it is actually done or not is dependent on the implementation. – nhahtdh Jan 12 '13 at 15:16
Even if it in theory can do any kind of optimization, it is silly bordering to dangerous to expect that it will. – Johan Kotlinski Jan 12 '13 at 15:18

Peter Lawrey · Answer 4 · 2013-01-12T16:14:20.740

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)

Why does this recursive fibonacci function run so poorly?

4 Answers4