Fibonacci Iterative vs Recursive

When we talk about the algorithms, then we can’t ignore the Fibonacci Series. There are numerous ways to solve a problem, but a good programmer is the one who does it by adopting the method which performs well in the worst-case scenario.

We are going to discuss two approaches here for the Fibonacci series, one is iterative and other is recursive.

Let’s start with the problem. Find out the Fibonacci value by the position. For example

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

So what is the value of 3rd position: 2, what is the value of 8th position: 21, we start the position from 0.

Recursive Approach

function fibonacciRecursive(n){
  if(n < 2){
    return n;
  }
  return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);
}
fibonacciRecursive(8);

Iterative Approach

function fibonacciIterative(n){
  let arr = [0,1];
  for(let i=2;i <= n; i++){
    arr.push(arr[i-1] + arr[i-2]);
  }
  return a[n];
}
fibonacciIterative(8);

Now let’s talk about the difference between both:

In the Recursive approach, when the position will be bigger, it will perform worst. The Big Notation of Recursive Fibonacci here is Exponential, ie, 0(2^n). While Iterative will linear time complexity, ie, o(n).

Why does Recursive Fibonacci have Exponential time complexity?

Because if we look into its process it’s making a tree kind structure.

So its structure will go bigger and bigger as the position increases. And it is worst for the worst scenarios.