DEV Community

Cover image for The optimal approach to find the nth Fibonacci number using recursion in Java
Sumant Kumar
Sumant Kumar

Posted on

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);
        }
    }
Enter fullscreen mode Exit fullscreen mode

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 at 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);
        }
    }
Enter fullscreen mode Exit fullscreen mode

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

Top comments (2)

Collapse
 
manju4ever profile image
Manjunath Desappa • Edited

Why would you want to take so much pain with recursion. You can do this with O(1) time with the following code. You can apply the same technique for a range or Nth fibonacci.

fib(n) = (Ψ ^n - (1 - Ψ)^n) / sqrt(5), where Ψ = 1.618

Collapse
 
sumant4ssm profile image
Sumant Kumar • Edited

This won't give you correct result after n=70.