Question

Dynamic Programming.

Consider the Fibonacci series

F(0) = 1; F(1)=1; F(n)=F(n-1)+F(n-2)

Define the Dynamic Programming algorithm for calculating F(5) . How does it compare with the recursive algorithm?

in java

Answer 1

Dynamic Program for fibonacci series:

class Main{
    public static void main(String args[])  
    {    
     int n1=1,n2=1,n3,i,n=5;    
     System.out.print(n1+" "+n2);//printing 0 and 1    
        
     for(i=2;i<=n;++i)//loop starts from 2 because 0 and 1 are already printed    
     {    
        n3=n1+n2;    
        System.out.print(" "+n3);    
        n1=n2;    
        n2=n3;    
     }    
      
    }
}  

Output:

Using Recursion:

class Main{
    public static int fibonacci(int n){
        if(n == 0 || n == 1){
            return 1;
        }
      
        return fibonacci(n-1) + fibonacci(n -2); //tail recursion
    }
    public static void main(String args[])  
    {    
     for(int i=0; i<=5; i++){
            System.out.print(fibonacci(i) +" ");
        }
    }
}  

Output: