Solution to Fibonacci series by Recursion through Dynamic Programming

Solution to Fibonacci series by Recursion through Dynamic Programming

Context: In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:

• 1,1,2,3,5,8,13,21,34,55...

Here, the first two numbers in the Fibonacci sequence are 1 and each subsequent number is the sum of the previous two.

The sequence Fn of Fibonacci numbers is defined by the recurrence relation:

• Fn = Fn-1 + Fn-2 with Base values F1=1 and F2=1

Problem: Find the Fibonacci number at the given position entered by the user through Recursion.

Conventional Solution: 

package com.practice.recursion;

import java.util.Scanner;

public class Fibonacci
{
    public static void main(String...s)
    {
Scanner sc= new Scanner(System.in);
System.out.println("Please Enter the number");

int num=sc.nextInt();

int fibonacciNumber=getFibonacci(num);

System.out.println("The Fibonacci Number at Postion "+ num+" is:"+fibonacciNumber);

sc.close();

    }
    public static int getFibonacci(int n)
    {
if(n==1|| n==2)

{

           return 1;
}

return getFibonacci(n-1)+getFibonacci(n-2);

    }
 }

Output:

Please Enter the number

12

The Fibonacci Number at Position 12 is:144

The problem with this solution is that this solution will have serious performance issues for large numbers.

So we will use the technique of Memoization to reduce the time.

What we will do is, we will store each calculated Fibonacci in a storage array and use this value in the calculation of the upcoming calculation of Fibonacci.

Memoization Solution: 

package com.practice.recursion;

import java.util.Scanner;

public class Fibonacci
{
    public static void main(String...s)
    {
Scanner sc= new Scanner(System.in);
System.out.println("Please Enter the number");

int n=sc.nextInt();

int fibonacciNumber=fibonacciMemo(n,new int[n+1]);
System.out.println("The Fibonacci Number at Postion "+ n+" is:"+fibonacciNumber);
sc.close();

}

        public static int fibonacciMemo(int n, int strg[]) 
      {

if (n == 0 || n == 1) {

return n;

}

if (strg[n] != 0) {

return strg[n];

}

int fnm1 = fibonacciMemo(n - 1,strg);

int fnm2 = fibonacciMemo(n - 2,strg);

int res = fnm1 + fnm2;

strg[n] = res;

return res;

}

}

Please Enter the number

43

The Fibonacci Number at Position 43 is:433494437

PS: Try to notice that I have made a storage array of size equal to n+1.

The reason for that is the zeroth index value will contain the value of 0th Fibonacci and 43rd index value will contain the value of 43rd Fibonacci but to accommodate the 43rd value we should also have an index 43rd. And for the 43rd index, the array should be made of size 44 !!