//start adsense code //end adsense code

Recursion vs Iteration

by | Jun 22, 2017

Before beginning with the recursion vs iteration and pros/cons comparison, I advise you to go through the following prerequisites:

Recursion

Recursion is a process in which a function calls itself. It is used when a problem depends on solutions to smaller instances of the same problem. Read about it in detail here.  

StackOverflow Error

 

A stack is linear data structure where items can be added or removed only from its ‘head’. Computer languages maintain this stack and use it to store parameters and local variables. For example, have a look at the following function:

 

int add(int a, int b)
{
    return a+b;
}

 

Here, the language will allocate memories to variables a and b, along with the function definition in the stack. Now, if the function is recursive, the stack will start getting filled every time the function calls itself. Since there is a limit to stack, a time may come when the stack is full and when the code tries to allocate more memory in the stack, it gives us StackOverflow Error.  

Recursion vs Iteration Comparison

 

Can every Recursive solution be converted into an Iterative solution?

 

Yes. However, you may need to write a lot of code that the language already implements. For instance, while implementing preorder tree traversal or a search function in a Binary Search Tree, you might end up using a stack in order to convert recursive solution into an iterative one. This process usually increases the size of the code.

Recursion or Iteration, which is better?

 

In reality, there is no rule that one should choose one over the other. However, computers prefer iterative solutions over the recursive ones since they reduce computational cost(time, memory, etc). However, it might not be always possible to you to write iterative solutions. Although it’s not impossible, it would increase the size of your code significantly. Look it up yourselves, try solving Tower of Hanoi iteratively and you’ll know what I mean. 

In competitive programming, there is a limit to the size of input data. So do bat an eye at the constraints give on the input size, time limit and size of submission file. In case you are using Tail Recursion, it is, generally, easy to convert it into an iterative one without adding a huge number of lines of code. May the source be with you!

 

0 Comments

More from this Category