Recursion v/s Iteration

Recursion:

Recursion is a method of solving a problem by breaking it into small sub problems till the time it can be solved easily. It follows a divide and conquer approach and in a program, it is generally implemented by using a function which calls itself again and again till a certain baseline condition is met, when the baseline condition is met it provides a solution without recursion which then helps in solving the bigger sub problems.
Recursion function has two main parts: the recursive function and the base case. The base case is important as without it function would in theory repeat forever and would practically result in the stack overflow.

Recursion is extensively used as a programming strategy. Some of the examples where recursion is used are in solving the N Queen problem, Tower of Hanoi, Finding the sum of subset, etc.

Why use recursion?

• These algorithms are usually shorter, simpler and easier to debug than iterative versions.
• Many algorithms are defined recursively(like Tower of Hanoi), so they are easily implemented by recursion.
• Many data structures are naturally recursive (trees, for example) and so it is easy to use recursion on them.

Why avoid recursion?

• Recursive procedures have the overhead of function calls and thus are slower in comparison to iterative.
• If not implemented properly may cause a stack overflow.
• Aborting recursion can sometimes be problematic and even impractical.

Iteration:

Iteration or looping is a process of executing a set of instructions repeatedly until a condition is satisfied. The iteration statement includes the initialization, checking condition, execution instructions inside the iteration statement and finally the updating of the control variable.

In a program, iteration is implemented using a loop like for, while, do-while. It uses a simple variable to store control data and does not have the overhead of repeated function calls and thus is faster than the recursive function.

Why use iteration?

• It’s generally faster than recursion.
• Calculating the time complexity of iteration is easy.
• Aborting the algorithm is as easy and practical.

Why avoid iteration?

• Infinite iteration consumes CPU cycles and fills up memory space.
• It’s impractical to use a naturally recursive data structure like a tree.

How to make a choice?

We should consider a lot of factors while deciding on what algorithm to use:

1. Time and space complexity of algorithms.
2. Ease implementation of algorithms and practicality.
3. Code size and clarity.
4. We should use recursive algorithms on data structures that are naturally recursive.

As an example of the above consideration, a sum of subset problem can be solved using both recursive and iterative approach but the time complexity of the recursive approach is O(2N) where N is the total number of elements in the subset and in case of iterative approach it O(N*SUM). But going ahead we can see that implementation using recursion is much cleaner and easier. But due to such a big difference in complexity, an iterative approach may be considered as the preferred.