Java Recursive Fibonacci Sequence

Java recursive Fibonacci sequence

In fibonacci sequence each item is the sum of the previous two. So, you wrote a recursive algorithm.

So,

fibonacci(5) = fibonacci(4) + fibonacci(3)

fibonacci(3) = fibonacci(2) + fibonacci(1)

fibonacci(4) = fibonacci(3) + fibonacci(2)

fibonacci(2) = fibonacci(1) + fibonacci(0)

Now you already know fibonacci(1)==1 and fibonacci(0) == 0. So, you can subsequently calculate the other values.

Now,

fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5

And from fibonacci sequence 0,1,1,2,3,5,8,13,21.... we can see that for 5th element the fibonacci sequence returns 5.

See here for Recursion Tutorial.

Comparing recursive Fibonacci with recursive factorial

The first method calls itself recursively once, therefore the complexity is O(n). The second method calls itself recursively two times, so per recursion depth the amount of calls is doubled, which makes the method O(2ⁿ).

The difference between O(n) and O(2ⁿ) is gigantic, which makes the second method way slower.

Calculating the 50th number using the second method requires 2⁵⁰ = 1125899906842624 recursive calls. Using the first method requires just 50 recursive calls. (Note: Those numbers must not be exact. I've just added them to illustrate the magnitudes of the linear and the exponential approach.)

The important thing to understand here is that the second method calculates the fibonacci number of same ns multiple times. Look at the initial call that calls itself recursively with n - 1 and n - 2. When you look at the call with n - 1, you see that it calls itself with n - 2 and n - 3. Have you noticed the problem? The method got called with n - 2 two times already. It has even called itself with n - 3 two times already, when you look at the first call with n - 2. This will get worse and worse as the depth of the recursion increases.

Note that the first method doesn't call itself two times with any same value.

inefficient recursive code to produce Fibonacci number in java

This is primarily because of the fact that this implementation of generating Fibonacci numbers is extremely inefficient.

This particular algorithm grows exponentially instead of linearly because each call of Fibonacci branches off into two more calls and continues on this track. Thus, increasing the size of N heavily increases the time required to complete.

A better approach would be keep track of the previous values for computing the next value.

long fibbonaci(int n) {
    long c = 0, k = 1;
    for (int i = 0; i < n; i++) {
        k += c;
        c = k - c;
    }
    return c;
}

What is wrong with my Java recursive fibonacci function?

Your program calculates the Fibonacci number correctly. It's the last number printed, in the top-level call to fibonacci.

Some numbers are repeatedly printed because they are being calculated more than once. fibonacci(5) calls fibonacci(4) + fibonacci(3), which calls fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1), and we already have two separate recursive calls that have the same argument. There are more repeated calls as the recursive calls descend further.

For a low input such as 5, this is ok, but for higher numbers, you will have performance problems, because this algorithm is exponential in nature. The complexity is O(2ⁿ). Your current print statements are highlighting all the extra calculations that are being performed. You can remove them, but the algorithm is still exponential in complexity.

Even though your program is currently correct, it is possible to eliminate the exponential complexity, replacing it with linear complexity (O(n)), by storing the results of intermediate calls to fibonacci in an array. This way, each intermediate step is only calculated once.

Fibonacci Recursion Not working

Fib is recursively define as Fib(n) = Fib(n-1) + Fib(n-2).
Your program defines it as Fib(n) = Fib(n-1) + (n-2)

Answer:

int Fibonacci(int n) {

    System.out.println(n + "N");

    if (n <= 1) {
        return n;
    } else {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

}

Why Fibonacci recursive algorithm working too slow ?

The classic recursive implementation of fib is this:

int fib(int n) {
    if (n < 2)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

This function recurses so many times, it is used as an easy benchmark to measure function call efficiency in various languages, with a time complexity of O(φⁿ).

You want an iterative implementation that will perform like a charm:

int fib(int n) {
    int a = 0, b = 1, c = n;
    while (n --> 1) {  // (n --> 1) is parsed as (n-- > 1)
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

Recursion vs. Iteration (Fibonacci sequence)

For terseness, Let F(x) be the recursive Fibonacci

F(10) = F(9)                      + F(8)
F(10) = F(8)        + F(7)        + F(7) + F(6)
F(10) = F(7) + F(6) + F(6) + F(5) + 4 more calls.
....

So your are calling F(8) twice,
F(7) 3 times, F(6) 5 times, F(5) 7 times.. and so on

So with larger inputs, the tree gets bigger and bigger.

---

Related Topics