# Recursion vs Iteration

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

## Recursion

Requires a lot of memory, as it uses Stack.

The process of memory allocation and function calls takes time, hence, the approach consumes more time.

Reduces the ‘bulk’ of code.

## Iteration

- Relatively, it requires much less memory.
- The process does remove major time taking processes such as memory allocation and function call with return overheads, hence, is less time-consuming.
- The number of lines of code is large.

## 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!

# More from this Category

## Getting Started with Software Development

Insight on building a software.

## Codechef: KMXOR Solution

Codechef May Cook-off 2018: KMXOR editorial with Java implementation.

## Algorithm: Binary Search

Variations of the conventional binary search algorithm are discussed.

## Graph Traversal

This article explains breadth first traversal and depth first traversal in graph theory.

## Graph Theory

Terminology and methods to represent a graph are explained.

## Primality Sieves

Segmented Sieve, Sieve of Sundaram, Sieve of Atkin are discussed here.

## 0 Comments