Fibonacci series 

Write a function to generate the first N Fibonacci numbers or write a function to find the Nth Fibonacci number (iterative and recursive approach) are the most common coding questions on fresher interviews and homework.

Fibonacci series: 0, 1, 1, 2, 3, 5, 8, 13, 21...

Here, we'll see how we can solve these problems using both iterative and recursive approaches.

Find Nth Fibonacci number  - iterative way

In the iterative way, we just need to keep track of the two previous values, so that we can use them to calculate the next Fibonacci number:

public class Fibonacci {

  public int fbnIterative(int n) {
    if (n <= 1) {
      return n;
    }

    int first = 0;
    int second = 1;

    for (int i = 2; i <= n; i++) {
      int newNumber = (first + second); // calculate the next fibonacci number
      first = second; // set the first number to the value of second
      second = newNumber; // set second to be the newNumber
    }

    return second;
  }
}

In the for loop, we start from the number 2 since we already have values 0 and 1 saved as the first and second variables.

Find Nth Fibonacci number  - recursive way

In the recursive approach, we use a recursive function to calculate the Fibonacci number.

public int fbnRecursive(int n) {
  if (n <= 1) {
    return n;
  }

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

It might not be obvious what is going on here behind the scenes. 

When we are dealing with the recursion, it is best to draw on a whiteboard and keep track of the steps during execution.

It's important to note that the recursive approach has exponential time complexity, which can lead to performance issues for large values of n. The iterative approach is more efficient for such cases.

See here for more details on this question and also see how we can improve the solution:

https://www.java67.com/2016/05/fibonacci-series-in-java-using-recursion.html