How would you write a method or a function to find the nth Fibonacci number in the Fibonacci sequence?




Before we try to solve this problem, let’s quickly review what the Fibonacci sequence is in case you do not know. 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. And the problem specifically states that the function or method needs to return the nth element in the Fibonacci sequence, where the input to that function or method is n.

Find nth Fibonacci number using recursion

It looks like this problem can be solved recursively because of the fact that there will obviously need to be a lot of “sub-tasks” in the form of adding up the previous two numbers in the sequence to get the next number in the sequence. So, with that in mind, let’s work on coming up with a recursive solution.

Find the base case(s) for the recursive solution

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. So far, our incomplete method looks like this in Java:

Finding the nth Fibonacci number in Java:

int fibonacci(int n) {

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

//TODO: recursive case

}

Now we have to do the hard part – figure out how to write the recursive case for this method. Let’s think about how the Fibonacci sequence works – it simply sums up the previous 2 numbers to get the next number in the sequence. That actually sounds pretty simple to convert to recursion – since the 2 previous numbers would have values of n-1 and n-2 for their position in the sequence. This means that we can write something like fibonacci(n-1) + fibonacci(n-2) to get the value for the nth fibonacci number right? And the base case we showed above will help stop the recursion! So, with this in mind we can write something like this:

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

}

Find nth Fibonacci number without using recursion – only iteration

Because every recursive method or function can be made iterative as well (read here: Recursion vs iteration, let’s examine an iterative solution to this problem also.




Clearly, even in the iterative solution, we can return a 0 if n is 0, and if n is either a 1 or a 2 we should return a 1 – just look at the sequence again above if you need to be reminded why. But, what about calculating the fibonacci sum using a loop? Well, in the recursive case we go backwards – starting from the nth number we sum the n-1 and n-2 numbers until we hit a base case. But, using iteration it looks like we would have to go forwards instead of backwards – so our approach would have to be to start from the very beginning of the sequence and then to keep summing numbers until we reach the nth number in the sequence. And once we reach the nth number, we will of course have our answer.

So, with that in mind how do we start our iteration? Well, we should only start adding numbers in the sequence if n is greater than or equal to 3 – because we are already returning values for n less than 3. And, we will clearly need two variables to represent the previous 2 numbers in the sequence. Since we are starting at n equal to 3, those 2 variables should both be initialized to 1 in order to represent the first and second numbers in the sequence.

In the loop itself all we have to do is add the previous 2 numbers, save the sum of those 2 numbers along with the previous number and keep repeating this process until we get the nth Fibonacci number. Here is what the iterative solution to finding the nth Fibonacci number looks like in PHP:

Find nth Fibonacci number in PHP


function fibonacci($n) {

//0, 1, 1, 2, 3, 5, 8, 13, 21

/*this is an error condition
   returning -1 is arbitrary - we could
   return anything we want for this
   error condition:
*/
if($n <0)
return -1;

if ($n == 0)
return 0;

if($n == 1 || $n == 2)
return 1;

$int1 = 1;
$int2 = 1;

$fib = 0;

//start from n==3
for($i=1; $i<=$n-2; $i++ )
{
$fib = $int1 + $int2;
//swap the values out:
$int2 = $int1;
$int1 = $fib;
}

return $fib;

}

?>

And now we have our answers that allow us to find the nth Fibonacci number both iteratively and recursively.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

  • Joszy

    The more elegant solution to this will be
    int fibo(){
    return n<3? 1: f(n-1)+f(n-2)
    }