Limited access

Upgrade to access all content for this subject

Which of the below choices demonstrates correct code which memoizes the following recursive algorithm to compute Fibonacci numbers?

public static int fib(int n) {
   if(n == 0) // base cases
      return 0;
   if(n == 1)
      return 1;
   if(n > 1) // recursive case
      return fib(n - 1) + fib(n - 2);
}
A
int[] f; // memoization table

public static int fib(int n) {
   if(f == null || f.length < n + 1)
      f = new int[n + 1];
   if(n == 0) // base cases
      return 0;
   if(n == 1)
      return 1;
   if(n > 1) {  // recursive case
      if(f[n] != null)
         return f[n];
      return fib(n - 1) + fib(n - 2);
   }
}
B
int[] f; // memoization table

public static int fib(int n) {
   if(f == null || f.length < n + 1)
      f = new int[n + 1];
   if(n == 0) // base cases
      return 0;
   if(n == 1)
      return 1;
   if(n > 1) {  // recursive case
      f[n] = fib(n - 2) + fib(n - 1);
      return f[n];
   }
}
C
int[] f; // memoization table

public static int fib(int n) {
   if(f == null || f.length < n - 2)
      f = new int[n - 1];
   if(n == 0) // base cases
      return 0;
   if(n == 1)
      return 1;
   if(n > 1) {  // recursive case
      if(f[n] != null)
         return f[n];
      f[n] = f[n - 1] + f[n - 2]
      return f[n];
   }
}
D
int[] f; // memoization table

public static int fib(int n) {
   if(f == null || f.length < n + 1) {
      f = new int[n + 1];
      f[0] = 0; // base cases
      f[1] = 1;
   }
   if(f[n] != null || n < 2) // recursive case
      return f[n];
   f[n] = fib(n - 2) + fib(n - 1);
   return f[n];
}
Select an assignment template