Two different way of recursion

Question

I calculate fibonachi row in two different ways. Why fib1 executes much longer then fib2?

public class RecursionTest {

    @Test
    public void fib1() {
        long t = System.currentTimeMillis();

        long fib = fib1(47);

        System.out.println(fib + "  Completed fib1 in:" + (System.currentTimeMillis() - t));

        t = System.currentTimeMillis();

        fib = fib2(47);

        System.out.println(fib + "  Completed fib2 in:" + (System.currentTimeMillis() - t));

    }


    long fib1(int n) {
        if (n == 0 || n == 1) {
            return n;
        } else {
            return fib1(n - 1) + fib1(n - 2);
        }
    }


    long fib2(int n) {
        return n == 0 ? 0 : fib2x(n, 0, 1);
    }

    long fib2x(int n, long p0, long p1) {
        return n == 1 ? p1 : fib2x(n - 1, p1, p0 + p1);
    }
}

The output:

2971215073  Completed fib1 in:17414
2971215073  Completed fib2 in:0

Answer 1

Because both algorithms work entirely different. Let me show you this with fib(5).

if you call fib1(5), it internally calls fib1(4) und fib1(3), lets visualize that with a tree:

    fib(5)
  /       \
fib(4)   fib(3)

now, fib(4) internally calls fib(3) and fib(2).

So now we have this:

           fib(5)
          /       \
    fib(4)       fib(3)
    /  \          /  \
fib(3) fib(2)  fib(2) fib(1)

I think by now it is very obvious where this is going, you should be able to fill in the rest.

edit: Another thing you should notice here is, that it actually has to performe the same caclculation multiple times. In this picture, fib(2) und fib(3) are both called multiple times. And this gets worse if the starting number is bigger./edit

Now, let's take a look at fib2(5). It you call it with 0, it returns 0. Otherwise, it calls fib2x(n, 0,1) So, we have a call to fib2x(5,0,1). fib2x(n, 0,1) now internally calls fib2x(n-1, p1, p0+p1) and so on. So, lets see:

        
fib2x(5, 0,1) => fib2x(4, 1,1) => fib2x(3, 1, 2) => fib2x(2, 2, 3) => fib2x(1, 3, 5)

by then, it has reached the return condition and returns 5.

So, your algorithms work entirely different. The first one works recursively and from the top to the bottom. The second one starts at 1 and works his way up. Actually, it is more iterative then recursive (it was probably written recursive to throw you off). It keeps the already calculated values instead of discarding them and therefore needs to invoke far less calculations.

Answer 2

The reason is two algorithms have different runtime complexities:

• fib1 is in Ο(2ⁿ)
• fib2 is in Ο(n)

Answer 3

Ultimately, it's because fib2 only uses tail end recursion. It only makes one recursive call at the end. Thus there isn't any "branching" associated with the recursion and leads to a linear time solution. The fact that it's a tail call also leads to certain compiler/VM optimizations where the recursion can be converted into an iterative procedure with lower overhead.

fib1 uses another recursive call in addition to the tail-call which causes the running time to be exponential.

Answer 4

fib1 is an algorithm with O(2^n) runtime. fib2 is an algorithm with O(n) runtime.

The reason for this is pretty cool -- it's a technique called memoization. The work the program does is saved at each step, avoiding any extraneous calculation.

You can see it happen by unrolling the loop a couple more steps:

long fib2(int n) {
    return n == 0 ? 0 : fib2x(n, 0, 1);
}
long fib2x(int n, long p0, long p1) {
    return n == 1 ? p1 : fib2xy(n - 1, 1, 1);
}
long fib2xy(int n, long p0, long p1) {
    return n == 1 ? p1 : fib2xyz(n - 1, 1, 2);
}
long fib2xyz(int n, long p0, long p1) {
    return n == 1 ? p1 : fib2xyz(n - 1, p1, p0 + p1);
}

You can unroll this loop to any arbitrary number in the fibonacci sequence; each step builds on the calculation stored previously in the stack until n is depleted. This is in contrast to the first algorithm, which must redo this work at every step. Nifty!