# 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);

}
```

### One Thought on “Find nth Fibonacci Number in the Fibonacci sequence?”

1. sushant on August 4, 2015 at 1:12 am said:

use DP(memoization). get result in O(n) time.