No. 8 - Nth number in Fibonacci Series

Problem:

Implement a function which returns the nth number in Fibonacci series with an input n. Fibonacci series is defined as:

Analysis: It is a classic interview questions to get numbers in Fibonacci series. We have different solutions for it, and their performance varies a lot.

Solution 1: Ineffient recursive approach

Our textbooks take Fibonacci series as examples for recursive functions does not necessarily mean that recursion is a good solution for Fibonacci series. Interviewers may tell candidates that the performance of this recursive solution is quite bad, and ask them to analyze root causes.

FibonacciSeries.java

package com.meritmix.blog.algo;
/**
 * @author Ravi Yadav
 * This is copyright content of MeritMix.com
 * blog address is blog.meritmix.com 
 */
public class FibonacciSeries {
 public static void main(String[] args) {
  long number = new FibonacciSeries().fibonacci(7);
  System.out.println("result: "+number);
 }

 public long fibonacci(int n) {
  if(n <= 0)
         return 0;

     if(n == 1)
         return 1;

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

Let us take f(10) as an example to analyze the recursive process. We have to get f(9) and f(8) before we get f(10). Meanwhile, f(8) and f(7) are needed before we get f(9). The dependency can be visualized in a tree as shown below:

As you can notice above that there are many duplicate nodes in the tree. The number of duplicate nodes increases as n increases.

Solution 2: More practical solution with O(n) complexity

It is easy to optimize performance fortunately if we calculate from bottom. That is to say, we get f(2) based on f(0) and f(1), and get f(3) based on f(1) and f(2). We follow this pattern till we get f(n).

FibonacciSeriesIterative.java

package com.meritmix.blog.algo;

/**
 * @author Ravi Yadav
 * This is copyright content of MeritMix.com
 * blog address is blog.meritmix.com 
 */
public class FibonacciSeriesIterative {
 public static void main(String[] args) {
  long number = new FibonacciSeriesIterative().fibonacci(7);
  System.out.println("result: "+ number);
 }
 
 public long fibonacci(int n)
 {
     int result[] = new int[]{0, 1};
     if(n < 2)
         return result[n];

      long  fibNMinusOne = 1;
      long  fibNMinusTwo = 0;
      long  fibN = 0;
     for( int i = 2; i <= n; ++ i)
     {
         fibN = fibNMinusOne + fibNMinusTwo;

         fibNMinusTwo = fibNMinusOne;
         fibNMinusOne = fibN;
     }

      return fibN;
 }
}

Solution 3: Recursive solution 1 could be optimized to O(n) with cache

FibonacciSeriesWithCache.java

package com.meritmix.blog.algo;
import java.util.HashMap;
import java.util.Map;
/**
 * @author Ravi Yadav
 * This is copyright content of MeritMix.com
 * blog address is blog.meritmix.com 
 */
public class FibonacciSeriesWithCache {
 private Map<Integer,Integer>  fibNumbers= new HashMap<Integer,Integer>();
 public static void main(String[] args) {
  int number = new FibonacciSeriesWithCache().fibonacci(8);
  System.out.println("result: "+number);
 }

 public int fibonacci(int n) {
  if(n <= 0)
         return 0;

     if(n == 1)
         return 1;
     if(fibNumbers.containsKey(n)){
      return fibNumbers.get(n);
     }
     int number = fibonacci(n - 1) + fibonacci(n - 2);
     fibNumbers.put(n, number);
     
     return number;
 }

}

Back to Menu

Section