Topics In Demand
Notification
New

No notification found.

Understanding The Differences Between Iteration and Recursion in DSA
Understanding The Differences Between Iteration and Recursion in DSA

November 29, 2022

184

0

Recursions and iteration are part of data structures and algorithms. Every software developer should be knowledgeable about recursion and iteration because they are the fundamental ways to continually carry out a given set of instructions in any programming language. The straightforward application of recursion helps solve several interview questions in software engineering.

 

Recursion vs iteration

 

Let's try to understand these notions using a straightforward example before moving on to the formal definitions.

In essence, recursion is a function that calls itself.

In conclusion, there are two alternative ways to repeatedly carry out a set of instructions: recursion and iteration.

 

  • Recursion occurs when a function calls itself several times within its own code, repeatedly carrying out the instructions it contains.
  • Iteration occurs when a loop, such as a "for" loop or a "while" loop, repeatedly executes a sequence of instructions.

 

When to Use Recursion?

 

We occasionally run upon issues that are too complicated to be resolved immediately. Most of the time, we try to divide such issues into smaller parts. Then, we can work out a way to resolve these more straightforward issues before putting the whole thing together. Recursion is based entirely on this concept.

 

Recursion occurs when a function either directly or indirectly calls itself, and the function that does so is referred to as a recursive function. It is primarily employed when it is possible to formulate the answer to a larger issue in terms of smaller issues.

 

Let's outline the steps Leo must take in the scenario from above to obtain the necessary clue:

 

Step 1: Stop here if you've found the clue; otherwise, move on to step 2.

Step 2: Find a target to enter their dream and look for clues. Step 3 is next.

Step 3: Enter their dream using the machine. Go to step 1 now.

 

As we can see, there are three steps to the recursive solution for solving the problem. If we have already found the clue, the default scenario is that we end the recursion.

 

When to Use Iteration?

Iteration is the process of repeatedly carrying out a series of instructions until the condition governing the loop is false. Initialization, comparison, running statements during iteration, and changing the control variable are all included.

 

The correct controlling condition must be present throughout iteration; otherwise, the programme may enter an infinite loop.

 

Let's create an iterative software, for instance, to assist Leo in discovering his clue.

 

  • Step 1 is to compile a list of potential targets.
  • Step 2: Choose a target from the list while it still contains items and enters his dream.
  • Step 3: Proceed to step 2 if you do not understand the clue; otherwise, move on to step 4.
  • Step 4: Congratulations! You figured it out!

 

Important distinctions between iteration and recursion

 

Iteration and recursion are two different approaches to repeatedly carrying out a set of instructions. The key distinction between the two is that while in iteration, we use loops like "for" and "while," in recursion, we use function calls to repeatedly execute the statements inside the function body.

 

Example

Let's examine a straightforward factorial programme that uses recursion and iteration.

Time Complexity

  • In our recursive technique, each call consumes O(1) operations, and there are O(N) recursive calls overall. Because of this, factorial utilizing recursion has an O time complexity (N).
  • Our iterative technique has an O(N) time complexity due to the loop's O(N) iterations (N).

 

Space Complexity

  • In our recursive technique, each call consumes O(1) operations, and there are O(N) recursive calls overall. Because of this, factorial utilizing recursion has an O time complexity (N).
  • Our iterative technique has an O(N) time complexity due to the loop's O(N) iterations (N).

 

Strengths and Weaknesses of Recursion and Iteration

 

  • Iteration

 

  1. Strengths:

 

  • Without the overhead of function calls or the utilization of stack memory, iteration can be used to repeatedly run a group of statements.
  • Recursion takes longer and is less effective than iteration.
  • Iterative codes often have polynomial time complexity and are simpler to optimize.

 

  1. Weaknesses:
  • In loops, we can only go in one direction; we cannot move or transfer data from the current state to a previously executed state.
  • Using loops to navigate trees and graphs is challenging.
  • One iteration can only pass a certain amount of data, but recursion allows us to send as many arguments as we require.

 

  • Recursion

 

  1. Strengths:
  • When the solution to the current problem depends on the solutions to smaller, related problems, it is simpler to code the solution using recursion.
  • The formula for the number n is: (n-1) + (n-2) + (n-3) (n-2)
  • factorial(n) is equal to n * factorial (n-1)
  • The size and comprehension of recursive codes are both reduced.

 

  1. Weaknesses:
  • Recursion sacrifices time and space efficiency for simplicity.
  • Due to the overhead of function calls and control shifting from one function to another, it is much slower than iteration.

 

Problems with Recursion and Iteration

 

  1. You can anticipate questions about recursion and iteration during technical interviews using the following examples:
  2. Create a programme using recursion and iteration to discover the n-th Fibonacci number. Compare the solutions' spatial and temporal complexity.
  3. Create a computer program using recursion to solve the renowned Tower of Hanoi challenge. Consider utilizing iteration to solve it.
  4. Create a programme that traverses a tree in preorder, postorder, and order using both iteration and recursion.

 


 


That the contents of third-party articles/blogs published here on the website, and the interpretation of all information in the article/blogs such as data, maps, numbers, opinions etc. displayed in the article/blogs and views or the opinions expressed within the content are solely of the author's; and do not reflect the opinions and beliefs of NASSCOM or its affiliates in any manner. NASSCOM does not take any liability w.r.t. content in any manner and will not be liable in any manner whatsoever for any kind of liability arising out of any act, error or omission. The contents of third-party article/blogs published, are provided solely as convenience; and the presence of these articles/blogs should not, under any circumstances, be considered as an endorsement of the contents by NASSCOM in any manner; and if you chose to access these articles/blogs , you do so at your own risk.


© Copyright nasscom. All Rights Reserved.