Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Overhead
4.4.
Infinite Repetition
5.
Difference between Iteration and Recursion
6.
Frequently Added Questions
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

Author Nikhil Joshi
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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. 

Difference between Iteration and Recursion

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.
     

iteration-three-parts

  • 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.

Code in Java

  • 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);
   }
}


Output 

24


Explanation

understanding-iteration-in-examples

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.

parts-of-recursive-functions

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.

Code in Java

  • 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;
   }
}

 

stack-image-of-example

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.

terminating-condition

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.

Overhead

  • 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:

Iteration Recursion
Uses loops (for, while, do-while). Relies on function calls with repeated recursion.
Condition explicitly defined in loops. Base case defined within the recursive function.
Involves explicit control structures. Can express complex relationships more concisely.
Generally lower memory footprint. May consume more memory due to function call stack.
May be less concise, especially for complex tasks. Can offer clear expression, particularly for certain tasks.
No inherent recursive function calls. Fundamental use of recursive function calls.
Minimal reliance on the call stack. Heavy reliance on the call stack, potential for overflow.
Often more efficient for simple tasks. May be less efficient due to function call overhead.
Variables have wider scope within loops. Local variables in each recursive call, more isolated.
Generally easier debugging with loops. Debugging recursive calls can be challenging.
Suited for linear processes and simple tasks. Well-suited for problems with inherent recursive structures.
Requires explicit task switching in the loop. Implicit task switching through recursive calls.
Explicit initialization before the loop. Initialization handled through function parameters.

Frequently Added Questions

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:

  1. Length of a Linked List(Iterative and Recursive method)
  2. Diagonal Traversal of Binary Tree (Recursive and Iterative) - Coding Ninjas
  3. Data Structure
  4. Difference Between Compiler and Interpreter and Assembler

 

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!

Previous article
Add Two Numbers Represented by a Linked List
Next article
Sum of the Combination of Numbers | Part-1
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass