Do you think IIT Guwahati certified course can help you in your career?
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 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.
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; } }
You can also try this code with Online Java Compiler
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.
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.
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); } }
You can also try this code with Online Java Compiler
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.
Difference between Recursion and Iteration
The key differences between Recursion and Iteration in the table below for a better understanding:
Recursion
Iteration
Relies on function calls with repeated recursion.
Uses loops (for, while, do-while).
Base case defined within the recursive function.
Condition explicitly defined in loops.
Can express complex relationships more concisely.
Involves explicit control structures.
May consume more memory due to function call stack.
Generally lower memory footprint.
Can offer clear expression, particularly for certain tasks.
May be less concise, especially for complex tasks.
Fundamental use of recursive function calls.
No inherent recursive function calls.
Heavy reliance on the call stack, potential for overflow.
Minimal reliance on the call stack.
May be less efficient due to function call overhead.
Often more efficient for simple tasks.
Local variables in each recursive call, more isolated.
Variables have wider scope within loops.
Debugging recursive calls can be challenging.
Generally easier debugging with loops.
Well-suited for problems with inherent recursive structures.
Suited for linear processes and simple tasks.
Implicit task switching through recursive calls.
Requires explicit task switching in the loop.
Initialization handled through function parameters.
Explicit initialization before the loop.
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.
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:
85+ registered