Java interview question: Fibonacci Series

Fibonacci series is a sequence of numbers, in which, each number is the sum of it’s previous 2 numbers. The first 2 numbers in the sequence are by definition: 0 and 1.
For some reason, it seem like writing a Java function that returns Fibonacci number is favorited by interviewers. I really find it difficult to understand why an interviewer would ask this kind of question, since it is not a question that implies on any practical knowledge or experience and can be easily memorized.
But, anyway, let’s see how it is done:
There are 2 ways of writing this function: recursive and none recursive. Interviewers may ask to write both versions.
Let’s start with the recursive version, which is surprisingly simple. well… simple if do not try to debug it in your head, but think of the process in a more mathematical way. In general, I believe that solving recursion problems is much simpler if you think of the solution in an abstract way, rather than trying to figure what exactly going on on each iteration.
Well, this is how the recursive function looks like:

package com.bashan.blog.interview;
/**
* @author Bashan
*/
public class Fibonacci {
  public static int fibonacci1(int n)
  {
    if (n == 0)
    {
      return 0;
    }
    else if (n == 1)
    {
      return 1;
    }
    else
    {
      return fibonacci1(n - 1) + fibonacci1(n - 2);
    }
}
 
public static void main(String[] args)
  {
    System.out.println(fibonacci1(12));
  }
}

Note, that both 2 first numbers in the series are handled separately. The output of the test program is of course: 144.
This function can be shorten to a single line of code:

package com.bashan.blog.interview;
/**
* @author Bashan
*/
public class Fibonacci {
  public static int fibonacci2(int n)
  {
    return n == 0 ? 0 : (n == 1 ? 1 : (fibonacci1(n - 1) + fibonacci1(n - 2)));
  }
}

The none recursive version should always save the current and the previous number in order to calculate the next number in the series. Let’s see how it looks in Java code:

package com.bashan.blog.interview;
/**
* @author Bashan
*/
public class Fibonacci {
  public static int fibonacci3(int n)
  {
    int prevN = 0, currentN = 1;
    for (int i = 0; i < n; i++)
    {
      int saveCurrentN = currentN;
      currentN = prevN + currentN;
      prevN = saveCurrentN;
    }
   
    return prevN;
  }
}

Note, that we return prevN rather than currentN. This saves us for writing a logic to handle the case of n = 0.
Here is a Java class that contains all 3 functions.

Check out this cool infographic to learn more about Fibonacci series.