Fibonacci Problem with Recursion and Memoization

The problem statement is to calculate the nth value of the fibonacci series.

So first we will have a look at the Fibonacci Series. 0,1,1,2,3,5,8,13,21,34,55 …..

First value of fibonacci series is 0. Second value is 1

fib(0) = 0
fib(1) = 1

The generic formula for fibonacci series is :

The nth fibonacci number in fibonacci series is defined as :

 fib(n) = fib(n-1)+fib(n-2)

To track any kind of dynamic programming problem with recursion, we should first start visualizing a tree and calculate sub problems and base cases.

For example, we can analyze the recursion tree for fib(5).

As per the above formula, we can divide the problem in to further sub problems

fib(5) = fib(4) + fib(3)

Each of the sub problems can be divided into further subproblems.

fib(4) = fib(3) + fib(2)

fib(3) = fib(2) + fib(1)

Now we have reached to a subproblem where the inputs are base case.

so fib(5)=5 as shown in Tree for Fib(5)

Java Program for Recursive Solution.

public class Solution {
  public static void main(String[] args){
   //Calling Fib Function for different values : 3,4,40,45
   int[] input = {3,4,40,45};
   for(int num : input) {
      Instant start = Instant.now();
      int result = new Solution().fib(num);
      Instant finish = Instant.now();
      long timeElapsed = Duration.between(start, finish).toMillis();
      System.out.println("fib("+num+") = "+result+",Total time taken = "+timeElapsed);
    }
  }
  public int fib(int n){
    if(n == 0){
       return 0;
    }
    if(n == 1){
       return 1;
    }
    return fib(n -1)+ fib(n -2);
  }
}

When you run this program you will see the execution time is very high for higher values of input.

E.g. Sample output:

fib(3) = 2,Total time taken = 0
fib(4) = 3,Total time taken = 0
fib(40) = 102334155,Total time taken = 511
fib(45) = 1134903170,Total time taken = 4768

Time Complexity

• The height of the tree is n. When you look at the above tree, at each level the execution is increasing by (2^level) times. Hence time complexity can be represented as 2^n. Time complexity : O(2^n)
• Space complexity : O(n) : The space complexity is O(n) because at any point of time, there can be maximum n number of methods in stack.

Question : In recursive flow, do you see any repeating sub problems?

Let us consider back fib(5) tree again.

Here if you see fib(3) is calculated two times.

Memoization

Here comes the enhanced version of the above solution to memoize the solutions and use it to for same sub problems.

Enhanced Solution with memoization : Here in this solution we memoize already calculated fibonacci values and use it for same subproblem again. In Java we can use a Map where key is the number and value is the calculated value of fibonacci.

public class Solution {
  public static void main(String[] args){
   //Calling Fib Function for different values : 3,4,40,45
   int[] input = {3,4,40,45};
   for(int num : input) {
      Map<Integer,Integer> memo = new HashMap<>();
      Instant start = Instant.now();
      int result = new Solution().fib(num,memo);
      Instant finish = Instant.now();
      long timeElapsed = Duration.between(start, finish).toMillis();
      System.out.println("fib("+num+") = "+result+",Total time taken = "+timeElapsed);
    }
  }
public int fib(int n,Map<Integer,Integer> memo){
    if(memo.containsKey(n)) {
       return memo.get(n);
    }
    if(n == 0){
       return 0;
    }
    if(n == 1){
       return 1;
    }
    int result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.put(n, result);
    return result;
  }
}

Test Results:

fib(3) = 2,Total time taken = 0
fib(4) = 3,Total time taken = 0
fib(40) = 102334155,Total time taken = 0
fib(45) = 1134903170,Total time taken = 0

Time Complexity for enhanced version:

After applying memoization, we can visualize the tree once again.

For every input it executes maximum n number of recursive calls and hence

TimeComplexity is O(n)

Space Complexity is O(n)

This approach is called top down approach of dynamic programming.

Happy Coding

Enjoy!!!