Question

java data structure question - Consider the following recurrence function"

f(1)=1; f(2)=2; f(3)=3; f(4)=2; f(5)=2

f(n) = 2 * f(n -1) + f(n – 5) for n >= 6

1. Write a program to demonstrate this recurrence relation (recursive method) and demonstrate it for the values n = 6, 7, 10, and 12;

2. Create a second method that solves the same problem using an iterative solution. Modify your test program to show that both the recursive method and the iterative methods produce the same results.

Answer 1

java code

public class MyClass {
    public static void main(String args[]) {
      // recurive
      System.out.println("Using recursive function");
      System.out.println("At n=6 f(6) = " + recursive(6));
      System.out.println("At n=7 f(7) = " + recursive(7));
      System.out.println("At n=10 f(10) = " + recursive(10));
      System.out.println("At n=12 f(12) = " + recursive(12));
      
      System.out.println(" ");
      // iterative function calling
      System.out.println("using iterative function");
      System.out.println("At n=6 f(6) = " + iterative(6));
      System.out.println("At n=7 f(7) = " + iterative(7));
      System.out.println("At n=10 f(10) = " + iterative(10));
      System.out.println("At n=12 f(12) = " + iterative(12));
    }
    
    // recurssive function
    public static int recursive(int n)
   {
      if (n == 1)
        return 1;
      else if (n == 2)
        return 2;
      else if (n == 3)
        return 3;
      else if (n == 4)
        return 2;
      else if (n == 5)
        return 2;
      else
        return 2*recursive(n-1)+recursive(n-5);
      
   }
   
    // Iterative function
    public static int iterative(int n)
   {
      int arr[]; 
      arr = new int[n]; 
      arr[0]=1;
      arr[1]=2;
      arr[2]=3;
      arr[3]=2;
      arr[4]=2;
      int i = 6;
      while(i<=n)
      { arr[i-1] = 2*arr[i-1-1] + arr[i-1-5] ;
        i++;
          
      }
      
      return arr[n-1];
   }
}

output screenshot