public class RecursiveFibonacci
{
	private static long count;				// used to count the number of recursive calls per attempt
	public static void main(String[] args)
	{
		count=0;
		System.out.println("The 8th element in the Fibonacci sequence is " + fib(8) + " which took " + count + " recursive calls.");		// fib(8) calls fib 41 times
		count=0;
		System.out.println("The 14th element in the Fibonacci sequence is " + fib(14) + " which took " + count + " recursive calls.");		// calls fib 753 times
		count=0;
		System.out.println("The 23rd element in the Fibonacci sequence is " + fib(23) + " which took " + count + " recursive calls.");		// calls fib 57313 times
		count=0;
		System.out.println("The 40th element in the Fibonacci sequence is " + fib(40) + " which took " + count + " recursive calls.");		// calls fib 204668309 times!
	}
	
	public static int fib(int n)
	{
		count++;						// used to count number of recursive calls, not used to compute fib value
		if(n==1||n==2) return 1;		// base case
		else return fib(n-1)+fib(n-2);	// recurrence
	}
}