Asim

This is Asim, a full stack web developer, a Toastmaster, and Ninja too. Passionate about building and learning new technologies. Any problem? wanna fight? then write your anger at: me@asimplify.com +(92)345 5306849

Categories
Tags

Which one is Better: Recursion or Iteration?

Which one is Better: Recursion or Iteration?

I have been developing software for many years now, and in my student days, we use to solve problems using the iterative approach or some time with recursion. I have never seen myself looking into the background how things work at the end, which one suits the best in the current scenario. I use then to solve my problems as I was taught.

But in professional life, and most specifically when you are dealing with complex logical problems where your ever memory usage is very critical or maybe in some cases, you don’t know how much my solution gonna take the memory you have to take some serious steps even before using recursion or iteration.

So why are you here? Let me tell you, I will try to explain my experience here, about

  • What is Recursion?
  • What is Iteration?

And we will see some examples here, and try to think which one either recursion or iteration suits best in the current scenario.

So, oil your engine and start that, and please wore your helmet also, because you may not like some of the things I will discuss here. Safety measure is good to have before I try to punch you :p

Let’s get started.

What is Recursion?

In basic English terms: recursion is the repetition of any application. Application means any code or chunk of code that may perform some feature.

Recursion in programming technique in which one method make a call to itself to solve some kind of problem.

What is Iteration?

Iteration is actually the synonyms of recursion in plain English.

Which is Better: Recursion or Iteration?

Let’s suppose you implement some algorithm, the implementation of recursive solution can be much more readable and elegant than an iterative solution( but in some cases, recursive solution is much more difficult to understand)

Recursion consumes more memory than solution build with iteration. If your solution has too many recursive calls a stack overflow exception may occur.

Fibonacci Example

        static long FibonacciCalculator(int n){
           if(n <=2){
           return 1;
           }
           return FibonacciCalculator(n-1)+FibonacciCalculator(n-2);
        }

Let say if call above function with value 12 it will return you 144. Working perfectly fine, right? But does this above solution is effective in terms of cost?

Let’s run this above function with input 100 the result will take much time that none of us wants to wait for that long. The reason is it is the extremely inefficient solution. Each call will lead to two more calls and each one of the leads to two more and so on.

Or which one this above solution is? Is this Recursive or Iterative?

Many of you say that above example is Recursive one, but it is Interaction, it’s an actually classical example of bad usage of recursion.

So, What’s the Good usage of Recursion

Example of Recursion

Let’s write the above calculating Fibonacci number again, but now with the Good usage of recursion.

public static void FibonacciCalculator(int a, int b, int counter, int number)
{
    Console.WriteLine(a);
    if (counter < number) FibonacciCalculator(b, a+b, counter+1, number);
}

source

Did you see the difference? First one is exponential time later one is linear.

Example of Iteration

Similarly, we can solve the above same problem with the iterative approach, in which we just need to have a previous and current value to calculate the next one.

static int pre = 1, next = 1, result = 0;
        public static int FibonacciCalculator(int n)
        {
            for (int i = 2; i < n; i++)
            {
                result = pre + next;
                pre = next;
                next = result;
            }
            return result;
        }

You can see simple elegant solution, It is effecient and does not require extra memory.

The debate is when to use recursion and when to use an iterative approach.

Recursion should be avoided unless you are damn sure what the code will do behind the scene, Recursion is very powerful until you know what could be the possibility of your using if you are unaware if you didn’t brainstorm about the solution before using this. The bullet will come back and hits you very very hard.

Comments

comments

Asim
asimaslam.kh@gmail.com
  • There are some cases where you can only go with recursion, for example, tree traversals… So it will not be a matter of choice there…

Please wait...

Have courage to interact?

Any problem? Wanna fight? Get yourself subscribe first.