The Fibonacci sequence {fib}i≥1 is defined recursively as follows: fib(1) = 1, fib(2) = 1 and, fib(n) = fib(n-1) + fib(n-2) for n ≥ 3. The numbers in the Fibonacci sequence are called the Fibonacci numbers, for example: {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …} Implement an efficient function in Java that returns the nth (n ≤ 90) Fibonacci number. Example: fib(9) = 34. long fib(int n)

// Create a class header definition

public class Fibonacci {

   //Create a method fib to return the nth term of the fibonacci series

   public static long fib(int n){

       //when n = 1, the fibonacci number is 1

       //hence return 1

       if (n <= 1){

           return 1;

       }

       //when n = 2, the fibonacci number is 1

       //hence return 2

       else if(n == 2){

           return 1;

       }

       //at other terms, fibonacci number is the sum of the previous two

       //numbers

       //hence, return the sum of the fib on the previous two numbers - n-1

       // and n-2

       else {

           return fib(n-1) + fib(n-2);

       }

   }

   //Create the main method to test the fib() method

   public static void main(String[] args) {

       // Test the fib method with n = 9        

       System.out.println(fib(9));

   }

}

34

The program above has been written in Java and it contains comments explaining each line of the code. Kindly go through the comments.

The actual lines of code are written in bold face to distinguish them from comments.

Also, a sample output of a run of the program has been provided.