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

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.