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:
		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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation