Find nth Fibonacci Number in the Fibonacci sequence?

In the Fibonacci sequence, the first two numbers are 0 and 1 and each number after that is the sum of the previous two numbers in the sequence. So, the sequence looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21… and so on. The “0″ in the sequence is considered to be the 0th element, the first “1″ is considered to be the 1st element, the 2 is the 3rd element, etc.

It should be very clear that if the input to our method is a 0, then we will return a 0 because the 0th element in the sequence is a 0. Likewise, if n is 1, then we will have to return a 1. These 2 scenarios are the base cases for our recursive method.

int fibonacci(int n) {

	//Error condition:
	if(n<0)
		return -1;

	//Base cases:
	else if (n==0)
		return 0;
	else if (n==1) 
		return 1;

	else if (n>1)
		return fibonacci(n-1) + fibonacci(n-2);

}