1.
Introduction
2.
What is Iteration?
2.1.
Code in Java
2.2.
Java
2.3.
Output
2.4.
Explanation
3.
What is Recursion?
3.1.
Code in Java
3.2.
Java
4.
Comparative Analysis of Recursion and Iteration
4.1.
Time Complexity
4.2.
Usage
4.3.
4.4.
Infinite Repetition
5.
Difference between Iteration and Recursion
6.
6.1.
Is recursion is always better than iteration?
6.2.
What are the critical components of recursion?
6.3.
What is the advantage of recursion over iteration?
6.4.
How do you convert iteration to recursion?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Difference between Iteration and Recursion

Nikhil Joshi
0 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## Introduction

In the realm of programming, two fundamental concepts for solving problems emerge: iteration and recursion. These approaches, while distinct in their methodologies, share the common goal of executing a set of instructions repetitively.

In this article, we will briefly discuss Iteration and recursion. We will take the example of the sum of elements in a given array. We will solve the problem using Iteration as well as recursion. We will then learn about the "difference between Iteration and recursion".

Let's start!

## What is Iteration?

As the name suggests, Iteration can be defined as executing multiple statements repeatedly until a termination condition reaches.

• Iterative code may have some initialisation statements, including statements to increment some variables.

• It must have some terminating statements besides the Initialisation and increment statements.

• Iteration is implemented through a loop (ex-for loop, while loop, do while loop ). The loop body contains the statement we want to execute multiple times.

• It is a must to have a termination statement for a loop, or it will end up in infinite execution of statements.

• The iterative procedure does not require any additional memory stack as required in case of recursion, discussed later.

• Iteration has no extra memory overhead and generally has better time complexity than recursion.

Let's take the example of the sum of elements in a given array.

Following is the Java program for the example provided.

• Java

### Java

``public class SumOfElementsInArray {    public static void main(String[] args) {        // Given array        int[] arr = {2,5,14,3};        // totalSum will store the sum of elements of element at last of loop execution        int totalSum = 0;        int n = arr.length; // stores length of array        for(int i=0; i<n; i++){            // currElement stores current element (ith element) of array            int currElement = arr[i];            // we are adding currElement to our final sum.            totalSum += currElement;        }        System.out.println(totalSum);    }}``

24

### Explanation

In our example, Iteration will stop when 'i' becomes equal to 4, the terminating condition (i < n, n = 4).

Now that you have understood Iteration let us look at what recursion is and how it differs from an Iteration.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## What is Recursion?

Recursion occurs when a function calls itself as a subroutine program. Recursion solves problems by dividing complex tasks into similar but manageable subtasks.

For example, We can divide the task of finding a node under the tree. We can check if the root node is the one we seek. If not, then we can check the left and right trees recursively.

In Java, method calls are implemented through the stack. You push the arguments in the stack one by one and invoke the method. When it is done, the arguments are consumed, and in their place, the result of the method is stored.

A recursive function call stops the execution of the current function and pushes a new instance of function in the stack, and invokes the newly instanced function.

Recursive codes are longer. They are easier to write once the subtask is cleared. Recursive codes are generally used along with memoisation for dynamic programming tasks.

Recursion requires extra memory space for the stack, making it less efficient than Iteration.

Let's take the example of the sum of elements in a given array.  Following is the Java program for the example given.

• Java

### Java

``public class SumOfElementsInArray {    public static void main(String[] args) {        // Given array        int[] arr = {2,5,14,3,67,8};        int n = arr.length; // stores length of array        // totalSum will store the sum of elements of element at last of loop execution        // calling sumOfArray will return sum from 0 to arr.length        int totalSum = sumOfArray(arr,0);        System.out.println(totalSum);    }    // sum of array will return sum from currentIndex to arr.length    private static int sumOfArray(int[] arr, int currentIndex){        // when currentIndex is equal to arr.length , then no        // element is left and hence, it will return 0.        if(currentIndex == arr.length){            return 0;        }        int sumAfterCurrentIndex = sumOfArray(arr,currentIndex+1);        return arr[currentIndex] + sumAfterCurrentIndex;    }}``

You can see the recursive call stack in the IntelliJ Idea debugger. The stack will use extra memory resources to store the content of each function call.

The loop will terminate when the current index equals arr.length. You can see that we are calculating the sum backwards in this recursion example. Basically, we are using S(i) = arr[i] + S(i+1).  Notice that to calculate S(i), we will first require S(i+1).

After discussing Iteration and recursion, we will list the difference between Iteration and Recursion.

## Comparative Analysis of Recursion and Iteration

### Time Complexity

• Recursion: Can lead to higher time complexity due to the overhead of function calls and the potential for repeated computations. However, certain problems may have concise recursive solutions.

• Iteration: Often exhibits lower time complexity, as loops typically involve fewer overheads compared to recursive function calls. It is usually more efficient for repetitive tasks.

### Usage

• Recursion: Ideal for problems that can be naturally divided into smaller, similar subproblems (e.g., tree traversal, sorting algorithms). It promotes elegant, concise code for certain scenarios.

• Iteration: Preferred for tasks requiring repetitive execution where a step-by-step approach is more intuitive. It is commonly used for linear processes and can be more straightforward for certain algorithms.

• Recursion: Introduces additional overhead through function calls, parameter passing, and maintaining a call stack. This can lead to increased memory usage and may impact performance.

• Iteration: Generally incurs lower overhead, making it more memory-efficient and faster in many cases. Loops directly control the flow, reducing the need for additional function calls.

### Infinite Repetition

• Recursion: Prone to the risk of infinite recursion if not properly handled, leading to stack overflow errors. Requires a base case to terminate the recursive calls.

• Iteration: Typically less susceptible to infinite repetition, as loops rely on explicit conditions for termination. It offers better control over the number of repetitions.

## Difference between Iteration and Recursion

The key differences between iteration and recursion in the table below for better understanding:

### Is recursion is always better than iteration?

No, recursion isn't always superior. The choice depends on factors like problem complexity, readability, and efficiency. While recursion offers elegance for certain tasks, iteration may be more efficient for straightforward processes.

### What are the critical components of recursion?

A recursive function must call itself. It is mandatory to have a base case. The state must be changed during the function call, or it will go on infinite.

### What is the advantage of recursion over iteration?

Recursion excels in expressing complex problems concisely, often mirroring mathematical relationships and promoting elegant code. It's beneficial for tasks naturally divided into smaller, similar subproblems.

### How do you convert iteration to recursion?

Identify the base case and transform the repetitive logic within the loop into recursive function calls. Pass necessary parameters and handle termination conditions within the recursive function.

## Conclusion

In conclusion, we have seen the difference between Iteration and Recursion. The main difference between Iteration and recursion is that Iteration is applied using loops, while recursion is applied using functions. We can write solutions for a problem using iterative and recursive methods. We have to trade off the simplicity of code, in the case of recursion, for better resource management, in the case of Iteration.

If you want to take a look at solutions to more complex problems using Iterative as well as recursive techniques, here are some articles for you:

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Learning!

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems