Question

There is a Java program that is missing one recursive function:

public class Fibonacci {
  /*          / 0                 when n = 0
   * fib(n) = | 1                 when n = 1
   *          \ fib(n-1)+fib(n-2) otherwise
   */
  public static int fib(int n) {
    return 0;
  }
  /* Fibonacci Test Framework
   *
   * Note, this takes a long time to compute fib(44).  
   */
  public static void main(String[] args) {
    int[] input   = { 11,    22,      33,        44};
    int[] expect  = { 89, 17711, 3524578, 701408733};
    boolean error = false;
    for(int i = 0 ; i < input.length; i++) {
      int answer = fib(input[i]);
      if(answer != expect[i]) {
        System.out.printf("ERROR: fib(%d) returned %d not %d.\n",
                          input[i], answer, expect[i]);
        error = true;
      }
    }

    if(error)
      System.exit(1);
    else
      System.out.println("Good Job!");
  }
}

Answer 1

The recursive function to calculate the Fibonacci is given below. The comments are provided for easy understanding.

  public static int fib(int n) {
        if((n == 0) || (n == 1))
                // If n = 0 or n =1 return 0 and 1 respectively. This is the exit condition for the recursive function.
                return n;
        else
                //If n > 1, then recursively call the fib function using the formula.
                //Here fib(n-1) will call the same fib function but with n-1 as the parameter.
                //And the fib(n-2) will call the same fib function but with n-2 as the parameter.
                //Finally when the results are retrived both are added and returned to the main function.
                return fib(n-1) + fib(n-2);
  }

The complete program is given below.

public class Fibonacci {
  /*          / 0                 when n = 0
   * fib(n) = | 1                 when n = 1
   *          \ fib(n-1)+fib(n-2) otherwise
   */
  public static int fib(int n) {
        if((n == 0) || (n == 1))
                // If n = 0 or n =1 return 0 and 1 respectively. This is the exit condition for the recursive function.
                return n;
        else
                //If n > 1, then recursively call the fib function using the formula.
                //Here fib(n-1) will call the same fib function but with n-1 as the parameter.
                //And the fib(n-2) will call the same fib function but with n-2 as the parameter.
                //Finally when the results are retrived both are added and returned to the main function.
                return fib(n-1) + fib(n-2);
  }
  
  /* Fibonacci Test Framework
   *
   * Note, this takes a long time to compute fib(44).  
   */
  public static void main(String[] args) {
    int[] input   = { 11,    22,      33,        44};
    int[] expect  = { 89, 17711, 3524578, 701408733};
    boolean error = false;
    for(int i = 0 ; i < input.length; i++) {
      int answer = fib(input[i]);
      if(answer != expect[i]) {
        System.out.printf("ERROR: fib(%d) returned %d not %d.\n", input[i], answer, expect[i]);
        error = true;
      }
    }

    if(error)
      System.exit(1);
    else
      System.out.println("Good Job!");
  }
}

The below are the screen shots of the program and the output. The screenshot if the output is from Windows environment, but the output will be same if it is tried from a Linux / Unix environment.