The optimal approach to find the nth Fibonacci number using recursion in Java

If you are a programmer or computer science student, you must be aware of the Fibonacci sequence and how we calculate it using recursion. No?

Ok, then, let's see the typical recursive approach.

private static int headRecursion(int n){
        if (n==1)
            return 0;
        if (n==2)
            return 1;
        else{
            return headRecursion(n-1)+headRecursion(n-2);
        }
    }

Well, the above approach is not an ideal approach, wondering why? Because it has exponential time and space complexities.

Time Complexity: > O(2^N) (Exponential Time Complexity) N -> index of nth fibonacci number

Since every value is made up of the previous 2 values, we need to find 2 values for finding any Fibonacci number. This gives rise to 2 calls every time in our recursion tree. The tree can have most n levels. This gives us at most 2^n nodes in the tree.

Space Complexity O(2^N) (Exponential Space Complexity) N -> index of nth fibonacci number

All the function calls are pushed into the function call stack. At any point in time at max 2^n, function calls are there in the call stack. Therefore, space complexity will be O(2^n)

Now, let's see the optimized recursive approach:

private static int tailRecursion(int n,int a,int b){
        if (n==1)
            return a;
        if (n==2)
            return b;
        else{
            return tailRecursion(n-1,b,a+b);
        }
    }

The initial values are a=0 and b=1. This is how we can optimally use recursion to find Fibonacci numbers!

In this case, there is just a single recursive function call which means that it is a faster approach - no need for two very similar recursive function calls(headRecursion(n-1) and headRecursion(n-2)). Java will not recalculate the same values several times.

Wondering what would be the time and space complexities in this approach?

Time Complexity: O(N) (Linear Time Complexity) N -> index of nth fibonacci number

For the nth number, there will be n function calls.

Space Complexity: O(1) (Constant Space Complexity), Isn't it amazing? N -> index of nth fibonacci number

At any point in time, at max 1, function calls are there in the call stack. Therefore, space complexity will be O(1)

Do you like the article or have any suggestions? Please like and comment on the article.