Question

hi

Answer 1

The first recursive algorithm which gorws exponentially is as follows:

​
public static int fibonacciArray[]=new int[50];
         // Traditional Fibonacci Algorithm
         public static int FibExponential(int x) {
                if(x==0 || x==1)
                        return x;
                return FibExponential(x-1) + FibExponential(x-2);
        }

​

The second recursive algorithm which grows in linear time is as follows:

public static int fibonacciArray[]=new int[50];​
​fibonacciArray[0]=1;
fibonacciArray[1]=1;

// Linear Fibonacci Algorithm
public static int FibLinear(int n){
                int fibValue=0;
                if(n==0 ){
                   return 0;
                }else if(n==1){
                   return 1;
                }else if(fibonacciArray[(int)n]!=0){
                   return fibonacciArray[(int)n];
                }else{
                   fibValue=FibLinear(n-1)+FibLinear(n-2);
                   fibonacciArray[(int) n]=fibValue;
                   return fibValue;
                }
        }

​

​

In order to run the code we need a Class which have a main method, The complete code which can be run is as follows:

import java.util.*;
class Demo {
         public static int fibonacciArray[]=new int[50];
         // Traditional Fibonacci Algorithm
         public static int FibExponential(int x) {
                if(x==0 || x==1)
                        return x;
                return FibExponential(x-1) + FibExponential(x-2);
        }

        // Linear Fibonacci Algorithm
        public static int FibLinear(int n){
                int fibValue=0;
                if(n==0 ){
                   return 0;
                }else if(n==1){
                   return 1;
                }else if(fibonacciArray[n]!=0){
                   return fibonacciArray[n];
                }else{
                   fibValue=FibLinear(n-1)+FibLinear(n-2);
                   fibonacciArray[n]=fibValue;
                   return fibValue;
                }
        }

        public static void main(String args[]) {
                fibonacciArray[0]=1;
                fibonacciArray[1]=1;
                int[] nlist = {5,10, 15, 20, 25, 30, 35, 40, 45};
                int index = 0;
                int[] fibarray1 = new int[nlist.length]; // to store the fibonacci numbers from FibLinear
                int[] fibarray2 = new int[nlist.length]; // to store the fibonacci numbers from FibExponential
                for (int n : nlist) {
                        if(index < nlist.length) {
                                fibarray1[index] = (int)FibLinear(n);
                                fibarray2[index] = FibExponential(n);
                                index++; 
                        }
                }
                System.out.println(Arrays.toString(fibarray1) + "\n" + Arrays.toString(fibarray2));
        }

}

Hope this works, Thank you