The Fibonacci sequence is a well-known mathematical sequence in which each term is the sum of the two previous terms. The sequence can be defined as follows:

fib(0) = 0

fib(1) = 1

fib(n) = fib(n-1) + fib(n-2) n>1

Write a recursive method to determine the nth number in the sequence. Put the method in a class called Fib. Note the method should be static. Think why.

File TestFib.java contains the tester. Save this file to your directory. Use it to test your recursive method.

To trace the recursive calling path, add a print statement at the beginning of your fib method that indicates the current parameter, e.g., Now control is in fib (3) if the parameter is 3.

// *******************************************************************

// TestFib.java

//

// A simple driver that uses the Fib class to compute the

// nth element of the Fibonacci sequence.

// *******************************************************************

import java.util.Scanner;

public class TestFib

{

public static void main(String[] args)

{

int n, fib;

Scanner scan = new Scanner(System.in);

System.out.print("Enter an integer: ");

n = scan.nextInt();

fib = Fib.Fib(n);

System.out.println("Fib(" + n + ") is " + fib);

}

}