Java recursive Fibonacci sequence

Question

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.

There are 2 issues with your code:

1. The result is stored in int which can handle only a first 48 fibonacci numbers, after this the integer fill minus bit and result is wrong.
2. But you never can run fibonacci(50).
   The code
   fibonacci(n - 1) + fibonacci(n - 2)
   is very wrong.
   The problem is that the it calls fibonacci not 50 times but much more.
   At first it calls fibonacci(49)+fibonacci(48),
   next fibonacci(48)+fibonacci(47) and fibonacci(47)+fibonacci(46)
   Each time it became fibonacci(n) worse, so the complexity is exponential.

The approach to non-recursive code:

 double fibbonaci(int n){
    double prev=0d, next=1d, result=0d;
    for (int i = 0; i < n; i++) {
        result=prev+next;
        prev=next;
        next=result;
    }
    return result;
}

In pseudo code, where n = 5, the following takes place:

fibonacci(4) + fibonnacci(3)

This breaks down into:

(fibonacci(3) + fibonnacci(2)) + (fibonacci(2) + fibonnacci(1))

This breaks down into:

(((fibonacci(2) + fibonnacci(1)) + ((fibonacci(1) + fibonnacci(0))) + (((fibonacci(1) + fibonnacci(0)) + 1))

This breaks down into:

((((fibonacci(1) + fibonnacci(0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))

This breaks down into:

((((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))

This results in: 5

Given the fibonnacci sequence is 1 1 2 3 5 8 ..., the 5th element is 5. You can use the same methodology to figure out the other iterations.

You can also simplify your function, as follows:

public int fibonacci(int n)  {
    if (n < 2) return n;

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