Comparing Fibonacci (Recursion vs Loop) And how to optimize Recursion in C++

Photo by Mario Mesaglio on Unsplash

What I will be discussing in this blog is the difference in computational time between different algorithms to get Fibonacci numbers and how to get the best results in terms of time complexity using a trick vs just using a loop.

Let’s start using Iteration. (loop)

//Iteration 
int FiboNR ( int n) { // array of size n
 int F[max];
 F[0]=0; F[1]=1;
 for (int i =2; i <=n; i++) {
  F[n] = F[n-1] + F[n-2];
}
 return (F[n]);
}

The previous algorithm takes n steps to execute so it’s time complexity is O(n) it’s a fairly good algorithm that doesn’t kill CPU, let’s see how we will going to run it with relatively big numbers in the main method.

Driver

Output

We can see from the output that using a loop with relatively big numbers won’t give the CPU a hard time executing the code.

Recursive Algorithm

On the other hand let’s take a look at the recursion algorithm

//Recursive
long FiboR ( int n) { // array of size n
  if (n==0 || n==1) {
    return (n);
  }
  else {
    return (FiboR (n-1) + FiboR(n-2));
   }
}

Driver

Output

We can see from the output that recursion took sometime processing higher values, from that we see that recursion in this case was not the best solution because recursive Fibonacci will take a long time as you are repeating the same call to an specific value several times, but how can we fix that?

we can modify the recursive algorithm and make it more efficient as if a value has been calculated you can store it and if the recursion is trying to calculate the value again you do not need to make recursive calls and return the value every time.

Modified Recursive Algorithm

//Modified Recursive
int fib(int n) {
  static std::vector<int> table; //our cache
  if (n <= 1) {
    return n;
  }
  else if (n >= table.size()) {
    table.resize(n+1); 
  }
  if (table[n] == 0) {
  // only recalc if we don't have a value
    table[n] = fib(n-1) + fib(n-2);
  }
  return table[n];
}

So what did we do here?

What we exactly did is that we store the calculated value then we compare to make sure that we won’t calculate it again if we already did and that will save a lot of time and it will execute the code much more efficiently.

This is called memoization or memoisation which is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Output

From the results we can see that our algorithm has gotten more efficient just by memoization.

Conclusion

Recursive can be very efficient and it can be very inefficient sometimes but there’s alway a away around it that will make the difference, we saw that we went from seconds to zero seconds by using a technique that will save us a lot of time and it will make your code much cleaner and bug free.