Finding the nth Fibonacci Number using Recursion

Fibonacci Sequence

Fibonacci sequence is the sequence in which each term is obtained after adding the previous two terms. 

Following is the Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

For example, the fifth Fibonacci number, which is 5, is obtained after adding the 4th and the 3rd Fibonacci number.

Finding the nth Fibonacci Number

Let’s learn how to find the nth Fibonacci number.

How to find the nth Fibonacci number?

The formula is easy. Let’s say fib(n) represents the nth Fibonacci number, then fib(n) can be obtained by adding the n-1th and n-2th Fibonacci numbers.

fib(n) = fib(n-1) + fib(n-2)

And this is exactly the recursive case of our program. 

return fib(n-1) + fib(n-2);

What’s the base case then?

The base case is the smallest possible problem. There are two small problems–the 0th Fibonacci number and the 1st Fibonacci number. If we need to know at least two values at a time, these can be our small problems. They will help in finding the 2nd Fibonacci number, the 3rd and so on. The following code shows the base case of our program:

if (n == 0) {
    return 0;
} else if (n == 1) {
    return 1;
}

The Complete Program

The entire program is as follows:

#include <stdio.h>

int fib(int n) {
    // Base case
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }
    // Recursive case
    else {
        return fib(n-1) + fib(n-2);
    }
}

int main() {
    printf("%d", fib(5));
    return 0;
}

Output:

5

Explanation:

This time we will not use the call stack to understand the flow of execution of the program. We are now quite familiar with what goes behind the scenes when we call a recursive function through the factorial example, but honestly, for the rest of our life, we may never use call stack to understand the flow of execution of a recursive function. There is one more easier and practical way to understand the working of any recursive function, and the name of the method is recursive tree method. Now, let’s understand the flow of execution of the Fibonacci program through this method.

First, fib(5) is called. As n = 5, the base case condition is not satisfied, therefore the recursive case will be executed. In the recursive case, the function is calling itself twice–fib(4) and fib(3). First, fib(4) will be resolved, and then fib(3). So, from fib(5), the control shifts to fib(4), and the recursive tree for this looks like the following:

Inside fib(4), according to its recursive case (which is return fib(3) + fib(2)), fib(3) and fib(2) need to be called because again the recursive case is satisfied. But, at a time, only one function call is possible, therefore first fib(3) will be resolved, and later fib(2). So, now the control shifts from fib(4) to fib(3). In the same way, from fib(3), the control shifts to fib(2) and then to fib(1). At this moment, the recursive tree looks like the following:

As we are within fib(1), the value of n is 1. At this point, one of the base case conditions is satisfied, and value will be returned to the caller of fib(1). From the recursive tree, one can easily observe who is the caller of fib(1). fib(2) has called fib(1) as there is the branch connecting both the function calls. Therefore, value 1 is returned to fib(2), and this means, in the recursive case of fib(2), fib(1) is replaced by the value 1. The following figure shows that we have returned successfully from fib(1) to fib(2). To remember the value returned by fib(1), I have mentioned the value close to fib(2) call as shown:

Now, see the recursive case of fib(2). The recursive case of fib(2) is return fib(1) + fib(0). This means fib(2) has called both fib(1) and fib(0). The fib(1) call is resolved, but what about fib(0)? You guessed it right! Now we need to shift the control from fib(2) to fib(0) so that we can resolve fib(0) as well. The following figure demonstrates the same:

Now, we are inside fib(0). As n = 0, the first base case condition is satisfied, and hence value 0 is returned to the caller of fib(0), which we know is fib(2) 😃. 

At this point, in the recursive case of fib(2), fib(0) is replaced by 0. We now have both the values, so we can add them. The recursive case (return fib(1) + fib(0)) looks like the following:

return 1 + 0   ≡   return 1 

So, value 1 is returned to the caller of fib(2) which is fib(3). 

From the recursive case of fib(3), which is fib(2) + fib(1), we can deduce that fib(3) has called both fib(2) and fib(1). We already know the value of fib(2), and we also know what fib(1) will return (value 1). In the recursive case of fib(3), fib(2) and fib(1) are replaced by 1. The result of addition is 2. Therefore value 2 will be returned to the caller of fib(3) which is fib(4). The following illustration shows how the process has been evaluated:

In the recursive case of fib(4), we have the statement: return fib(3) + fib(2). We already know that fib(3) is 2, and we have already calculated the value of fib(2). The value of fib(2) is 1, remember? This is the beauty of the recursive tree method. The entire recursive process is visible to us, and we can easily eliminate redundant calls if we already know their values. Although, I have drawn the complete recursive tree up to this point, but you don’t have to 🥳 

So, fib(3) + fib(2) = 2 + 1 = 3. Therefore, value 3 is returned to the caller of fib(4) which is fib(5). Now, we know, in the recursive case of fib(5), we have the statement:  return fib(4) + fib(3). The fib(4) is resolved, and the best part is we already know the value of fib(3) which is 2. So there is no need to call fib(3) recursively. Please remember, the recursive tree method is for our understanding of the recursion. So, we can eliminate the redundant steps whenever possible. The entire recursive tree looks like the following but remember you can always eliminate the redundant steps:

The recursive tree after eliminating the redundant calls look like the following:

So, what’s the final value of fib(5). It is equal to fib(4) + fib(3) = 3 + 2 = 5. So, the 5th Fibonacci number is 5, which is correct 🤘😎