What is iteration in programming?

Iteration Introduction

Often in an algorithm, a group of statements needs to be executed again and again until a certain condition is met, this is where we find the need for iteration.

The repeated execution of some groups of code statements in a program is called iteration.

We will be exploring the following concepts in Iteration:

• Tools of iteration
• Examples of Iterative code
• Analysis of Iterative code
• The correctness of Iterative code
• Problem-solving using Iteration
• Applications of Iteration
• Critical concepts to explore further
• Suggested Problems to solve

Tools of iteration

Loops are tools provided by programming languages to implement iteration. Generally, we use two different types of loops:

• for loop
• while loop

Note: Some languages there is an additional loop, i.e. a do-while loop.

for loop

This involves initializing the variable, defining the loop condition and implementing the increment/decrement statements.

for(loop initialization, loop condition, increment/decrement)
{
      // loop body
}

Loop body: A single statement or a block of statements.

Loop condition: any expression, and true is any nonzero value. The loop iterates while the loop condition is true.

while loop

A while loop repeatedly executes a target statement as long as a given condition is true. This requires pre-initialization of loop variables (if any), defining loop condition, writing loop body and increment or decrement statements.

loop variable initialization
while (loop condition)
{
     // loop body
     // loop variable increment/decrement
}

Examples of Iterative Code

Iteration Example: Increment the loop by 1

Find the maximum element in an array.

int largest(int A[], int n) 
{ 
    int i
    int max = A[0]
    for (i = 1; i < n; i++) 
    {
        if (A[i] > max) 
            max = A[i]
    }        
    return max
} 

Iteration Example: Two pointer approach

Reverse an array.

void reveseArray(int A[], int start, int end) 
{ 
    while (start < end)
    { 
        int temp = A[start]
        A[start] = A[end] 
        A[end] = temp
        start = start + 1
        end = end - 1
    }  
}     

Iteration Example: Increment the loop by 2

Sort an array in wave form

void sortWave(int A[], int n) 
{ 
    for (int i = 0; i < n; i=i+2) 
    { 
        if (i>0 && A[i-1] > A[i] ) 
            swap(A[i], A[i-1])
 
        if (i<n-1 && A[i] < A[i+1] ) 
            swap(A[i], A[i+1])
    } 
} 

Iteration Example: Exponential Increment

Print powers of 2 uptil 2^n

void printPowersOf2(int n)
{
    for ( int i = 1; i <= pow(2,n); i = i*2)
        print(i)
}

Iteration Example: Nested loops

Insertion sort in an array

void insertionSort(int A[], int n)
{
    for(int i = 1; i <= n-1; ++i )
    {
        int key = A[i]
        int j = i-1
        while (j >= 0 and A[j] > key )
        {
            A[j+1] = A[j]
            j = j - 1
        }
        A[j+1] = key
    }
}

Iteration Example: Two pointer approach

Merge two sorted arrays

void mergeSortedArrays(int A[], int B[], int n1, 
                             int n2, int C[]) 
{ 
    int i = 0, j = 0, k = 0
    while (i<n1 && j <n2) 
    { 
        if (A[i] < B[j]) 
        {
            C[k] = A[i]
            k = k + 1
            i = i + 1
        }    
        else
        {
            C[k] = B[j]
            k = k + 1
            j = j + 1
        }    
    }
    while (i < n1) 
    {
        C[k] = A[i]
        k = k + 1
        i = i + 1
    }    
    while (j < n2) 
    {
        C[k] = B[j]
        k = k + 1 
        i = i + 1
    } 
}  

Analysis of Iterative Code

Complexity Analysis in an iteration is relatively simpler compared to recursion. We basically need to calculate the total number of operations performed by the loop in the worst case with respect to the input size (conventionally denoted by n).

• A loop that runs a constant number of times is considered as O(1)
• The time complexity of a loop is considered as O(n) if the loop variables are incremented/decremented by a constant amount.
• The time complexity of nested loops is equal to the number of times the innermost statement is executed.
• The time complexity of a loop is considered as O(log n) if the loop variables are divided/multiplied by a constant amount.
• When there are consecutive loops, we calculate time complexity as a sum of time complexities of individual loops.

Correctness of Iterative Code

We use loop invariants to verify the correctness of the iterative algorithms. We must show three things about a loop invariants:

• Initialization: Here we show that loop invariant is true before the first loop iteration.
• Maintenance: Here we show that if loop invariant is true before an iteration of the loop, it remains true before the next iteration.
• Termination: Here we examine what happens when the loop terminates.

Example: Given a sorted array of n integers and given a number K, determines whether there is a pair of elements in the array that sums to exactly K.

Problem-solving using Iteration

1. Identify the condition which defines the working of the loop:

• If we know how many times the loop should run, conventionally we use a for loop.
• If we want the loop to break based on a condition other than the number of times it runs, we should use a while loop.

Note: The choice of the loop is purely based on conventions and can be chosen either way according to the convenience of the programmer.

2. Sometimes we use a loop variable to count how many times the loop runs. We need to initialize and define this loop variable. Also, define the increment/decrement condition for the loop variable.

3. Define the condition which terminates the loop

Note: Using a loop variable is optional while coding iteration. Iteration can be terminated based on a predefined state of some existing variable too.

Applications of Iteration

Iteration methodology has various applications in the programming world →

• Problem-solving in arrays, vectors, lists, strings, etc.
• Problem-solving using Stack, Queue and Priority Queue
• Bottom-up implementation of Dynamic Programming
• Implementation of greedy algorithms
• BFS traversal of tree and graph
• Problem-solving using Hash Table and BST
• Iterative Implementation of recursive code using stack

Critical concepts to explore further

• Advantages and disadvantages of iterative programming
• Different Types of the loop and its analysis
• Iteration vs Recursion comparison
• Two Pointer approach
• How infinite loop situation occurs in an iteration?
• How to convert and recursive code into iterative code and vice versa?

Suggested problems to solve

• Move zeroes to an end
• Wave Array
• Remove duplicates from sorted array
• Maximum j – i such that A[j] > A[i]
• Set Matrix Zeroes
• Spiral Matrix
• Rotate matrix
• Minimum Absolute Difference in an Array
• Container with Most Water

Happy Coding, Enjoy Algorithms!

AfterAcademy Data Structure And Algorithms Online Course — Admissions Open