What is an iteration in programming?
To solve a problem, sometimes, we repeat a particular code statement several times until a specific condition is satisfied. It is known as iteration, which allows us to "write code once" and "execute many times." In computer programming, iteration is often referred to as ‘looping’ because instead of repeatedly writing the same code, we can execute the same code a finite number of times. It provides code reusability and simplifies steps of problemsolving.
In data structure and algorithms, several problemsolving approaches are based on iteration. So a good grasp of the loop fundamental is essential for mastering these approaches. Here are some excellent examples of iterative problemsolving approaches:
 Building partial solution using a single loop
 Problemsolving using nested loop
 Two pointers approach
 Sliding window approach
 Problemsolving using a hashing
 Problemsolving using stack, queue, and Priority queue
 BFS traversal in a tree and graph
 The bottomup approach of dynamic programming
 Iterative backtracking using stack
Types of loops in programming
Iteration is implemented using the loop in programming languages, where we primarily use two types of loops: "for" loop and "while" loop.
Type1: 'for' loop in programming
We use the "for" loop when we know how many times the loop will execute. In other words, the "for" loop helps us to run some particular code statement defined number of steps.
Inside the for loop, we use a loop variable to control the execution of the loop, where the initial value of the variable decides the starting point. So, we start by initializing the loop variable to some value and checking whether the loop condition is true or not. If the loop condition is true, the code inside the loop body will execute. Then, we update the loop variable and move to the next iteration. This step will be repeated till the loop condition becomes false.
for (loop initialisation; loop condition; loop update)
{
loop body
}
Type 2: 'while' loop in programming
The "while" loop is used to execute the loop body until a specific condition is false. We mainly apply this idea when we don’t know how many times the loop will execute.
The while loop consists of a loop condition, a block of code as a loop body, and a loop update expression if required. First, the loop condition is evaluated, and if it is true, then the code within the loop body will be executed. This process repeats until the loop condition/expression becomes false. Thus, for better intuition, the while loop can be thought of as a repeating if statement.
loop initialisation
while (loop condition)
{
loop body
loop update
}
Special Notes
 There is also a third type of loop in programming: the dowhile loop. It is similar to the while loop, where loop execution is terminated based on some loop condition. But dowhile loop condition is tested at the end of the loop body.
 The dowhile loop is exit controlled, whereas the for and while loops are entry controlled loops.
 In the dowhile loop, the loop body will execute at least once irrespective of the test condition.
 It's an exercise for you to explore the implementation and properties of the dowhile loop.
Core elements of the loop in computer programming
 Loop initialization: Initialization of the loop variables used before starting the first iteration of the loop execution.
 Loop condition: This is a boolean expression calculated at the beginning of each loop iteration to determine whether the loop body will execute or stop.
 Loop body: The core part of the loop where we perform required operations to manipulate data at each iteration. There can be more than one code statement here.
 Loop update: We perform increment/decrement operations for the loop variable to control the repetitions of the loop.
So here is the basic flow of the loop execution:
 Loop conditions will be evaluated first.
 If the loop condition is true, then the loop body will run, the loop variable gets updated (increment/decrement operation), and the loop condition's value is reevaluated. The loop body will run as long as the loop condition will be true.
 As soon loop condition becomes false, we exit the loop and continue with the further code instructions.
How to design a correct iterative algorithm?
We should consider these critical steps to design and check the correctness of an iterative code in data structure and algorithms:
 Precondition: must be appropriately defined and true before the loop executes.
 Postcondition: must be appropriately defined and true after the loop terminates.
 Loop variant: An exit condition that controls the loop's execution must be appropriately defined to ensure loop termination.
 Loop invariant: The most critical aspect that is true before and after each iteration of a loop. The values of variables may change, but the loop invariant's truth does not vary.
Let's try to understand the above idea via some examples.
Example 1: finding the sum of all integers from 1 to n
Precondition: we need to define two variables: a variable i that acts as a loop counter and a variable sum to store the sum of all integers. We would like to do a sum from 0 to n, so at the start, we initialize both variables to 0, i.e., sum = 0, i = 1
Postcondition: After the loop termination, the value of the sum must be equals to the sum of all integers from 1 to n.
Loop variant: The loop should terminate when we have added all integers from 1 to n,i.e, i<= n. In other words, the loop should not terminate until we have added n to the sum.
Loop invariant: Now, we need to set the loop invariant so that when the loop terminates, we will have the correct output. As discussed above, the loop invariant must be true before and after each loop iteration.
 Before any ith iteration of the loop, the variable sum must be equals to the sum of all integers from 1 to i1.
 At the ith iteration, we add the value i to the sum (sum = sum + i) and increase the variable i by 1. This ensures that as we go through each iteration, the variable i would approach n and provide the sum of values from 1 to n after loop termination.
 After the ith iteration, the variable sum must be equals to the sum of all integers from 1 to i.
 The above invariant will continue till the end of the loop.
Solution Pseudocode
int findSum(int n)
{
int i = 1
int sum = 0
while (i <= n)
{
sum = sum + i
i = i + 1
}
return sum
}
Example 2: Finding the max element in an array
Precondition: we need to define two variables: a loop variable i that acts as a loop counter and a variable max to store the maximum of all integers. Before starting the loop to find the max value from X[0] to X[n1], we initialize max = X[0] and start the loop with i = 1. This precondition holds true when we enter the first iteration of the loop.
Postcondition: After the loop termination, the max value must store the max of all values from X[0] to X[n1].
Loop variant: The loop must terminate after finding the max of all integers from X[0] to X[n1]. In other words, the loop should not terminate until we have compared X[n1] to the max i.e. i <= n1 or i < n.
Loop invariant
Let's assume invariant is true after (i1)th iteration, i.e., max store the maximum of all integers from X[0] to X[i1]. We need to design instruction so that the invariant must be true after ith iterations of the loop  the variable max must be equal to the max of all integers from X[0] to X[i]. Here are the steps of the ith iteration:
 We compare max with new value X[i]. If (max < X[i]), it means we have found a value that is greater than the max of all the values from X[0] to X[i1]. In such a situation, we update the max value with X[i]i.e. max = X[i]. Otherwise, we ignore it, and the value stored in max is still the maximum of all integers from X[0] to X[i].
 We also increase i by 1 through each iteration to update the maximum from X[0] to X[n1] in the variable max.
Solution Pseudocode
int findMax(int X[], int n)
{
int max = X[0]
for (int i = 1; i < n; i = i + 1)
{
if (X[i] > max)
max = X[i]
}
return max
}
Some common error in writing loops
Infinite loops
An infinite loop occurs when a loop condition continuously evaluates to true or not making progress towards loop termination. It appears most of the time due to the incorrect update of the loop variables or some error in the loop condition. Usually, this is an error, but it's common for infinite loops to occur accidentally.
For example, we want to display the sum of all numbers from 5 to 10 via the following code and ended up with an infinite loop because we did not increment the loop variable. The loop variable remains the same through each iteration, and progress is not made towards loop termination.
int i = 5
int sum = 0
while (i <= 10)
sum = sum + i
Here is the correct version of the code:
int i = 5
int sum = 0
while (i <= 10)
{
sum = sum + i
i = i + 1
}
Other examples of the Infinite loop
Example 1: For i < 0, this goes into an infinite loop!
void infinteLoop(int i)
{
while (i != 0)
{
i = i  1
}
}
Example 2: here loop condition is "1" which is always true!
int i = 0
while(1)
{
i = i + 1
print(i)
}
But in some situations, an infinite loop can be used on purpose. For example, we use an infinite loop for the applications that continuously accept the user input and constantly generate the output until the user comes out of the application manually.
 An operating system is the best example of it. It runs in an infinite loop and performs tasks continuously. It only comes out of an infinite loop when the user manually shuts down the system.

We read from input a sequence of data and stop reading from the input as soon as a particular condition becomes true. The general structure of an input loop:
read the first element
while (element is valid)
{
process the element
read the following element
}
 Some online games execute in an infinite loop. The game will keep accepting the user requests until the user exits from the game.

A typical web server runs in an infinite loop as the server responds to all the client requests. It takes a request for a web page, returns a web page, and waits for the subsequent request. It will come out of an indefinite loop only when the admin shuts down the server manually.
while (true)
{
Read request
Process request
}
Another popular way is:
for ( ; ; )
{
Read request
Process request
}
OffByOne error in the loop
It is an error involving the boundary condition of the loop: the loop variable's initial value or the loop's end condition. This problem could arise when a programmer makes mistakes such as:
 Using <=" instead of "<" while checking the expression in the loop condition.
 Fails to consider that a sequence that starts at zero rather than one.
OffByOne Example 1
int X[5]
for (int i = 0; i <= 5; i = i + 1)
print(X[i])
The above program will result in an array out of bounds exception because we will try to display the result for X[5] and the upper bound of the array is only 4. This is because the index for the array starts at 0 instead of 1 in most programming languages. The correct code is displayed below.
int X[5]
for (int i = 0; i < 5; i = i + 1)
print(X[i])
OffByOne Example 2
 Case1: for (int i = 1; i < n; i = i + 1) { ... }
 Case2: for (int i = 0; i <= n; i = i + 1) { ... }
In the first case, the loop will be executed (n1) times and in the second case (n + 1) times, giving error offbyone. The loop can be written correctly as: for (int i = 0; i < n; i = i + 1) { ... }
Examples of Loop in programming
Single loop increasing by 1
Loop of finding the nth Fibonacci using the bottomup approach of DP
for(int i = 2; i <= n; i = i + 1)
Fib[i] = Fib[i  1] + Fib[i  2]
Kadane algorithm loop of finding maximum subarray sum
for (i = 1; i < n; i = i + 1)
{
curr_maxSum = max (curr_maxSum + X[i], X[i])
if(maxSum < curr_maxSum)
maxSum = curr_maxSum
}
Boyer–Moore voting algorithm of finding majority element in an array
for(int i = 0; i < n; i = i + 1)
{
if(count == 0)
majorityCandidate = X[i]
if(X[i] == majorityCandidate)
count = count + 1
else
count = count  1
}
Nested loops
Nested loop of the Bubble sort algorithm
for(int i = 0; i < n; i = i + 1)
{
for(int j = 0; j < n  i  1; j = j + 1)
{
if( X[j] > X[j+1])
{
temp = A[j]
X[j] = X[j+1]
X[j+1] = temp
}
}
}
Nested loop of the Insertion sort algorithm
for(int i = 1; i < n  1; i = i + 1)
{
int key = X[i]
int j = i  1
while (j >= 0 && X[j] > key)
{
X[j + 1] = X[j]
j = j  1
}
X[j + 1] = key
}
Nested loop of finding transpose of a square matrix
for (int i = 0; i < n; i = i + 1)
for (int j = i + 1; j < n; j + 1)
swap(X[i][j], X[j][i])
Single loop increasing by 2
Single loop of finding max and min in an array
while (i < n)
{
if (X[i] < X[i+1])
{
if (X[i] < min)
min = X[i]
if (X[i+1] > max)
max = X[i+1]
}
else
{
if (X[i] > max)
max = X[i]
if (X[i+1] < min)
min = X[i+1]
}
i = i + 2
}
Single loop of sorting an array in a waveform
for (int i = 0; i < n; i = i + 2)
{
if (i > 0 && X[i1] > X[i])
swap(X[i], X[i1])
if (i < n1 && X[i] < X[i+1])
swap(X[i], X[i + 1])
}
Single loop Increasing or decreasing by a factor of 2
Loop of exponential search in an unbounded array
while (i < n && X[i] <= key)
i = i*2
Loop of iterative Binary Search
while (left <= right)
{
int mid = left + (right  left)/2
if (X[mid] == key)
return mid
if (X[mid] < key)
left = mid + 1
else
right = mid  1
}
Loop of searching iteratively in a BST
while (root != NULL)
{
if (key < root>data)
root = root>left
else if (key > root>data)
root = root>right
else
return true
}
Two pointers loop: pointers moving in the opposite direction
Twopointers loop of reversing an array
while (left < right)
{
int temp = X[left]
X[left] = X[right]
X[right] = temp
left = left + 1
right = right  1
}
Two pointers loop of finding pair sum in a sorted array
while (l < r)
{
if(X[l] + X[r] == k)
return 1
else if(X[l] + X[r] < k)
l = l + 1
else
r = r  1
}
Two pointers loop: pointers moving in the same direction
Twopointers loop of merging algorithm in merge sort
while (i < n1 && j < n2)
{
if (X[i] <= Y[j])
{
A[k] = X[i]
i = i + 1
}
else
{
A[k] = Y[j]
j = j + 1
}
k = k + 1
}
Twopointers loop of partition algorithm in quicksort
for (int j = left; j < right; j = j + 1)
{
if (x[j] < pivot)
{
i = i + 1
swap(X[i], X[j])
}
}
Twopointers loop of finding loop in a linked list: Floyd algorithm
while (slow && fast && fast>next)
{
slow = slow>next
fast = fast>next>next
if (slow == fast)
return 1
}
Loop on stack and queue data structures
BFS Traversal of binary tree using queue
while (Q.empty() == false)
{
TreeNode temp = Q.dequeue()
print(temp>data)
if (temp>left != NULL)
Q.enqueue(temp>left)
if (temp>right != NULL)
Q.enqueue(temp>right)
}
Preorder traversal in binary search using stack
while (S.empty() == false)
{
Treenode temp = S.pop()
printf(temp>data)
if (temp>right)
S.push(temp>right)
if (temp>left)
S.push(node>left)
}
Critical ideas to think!
 Sometimes we forget to initialize and update the variable used in the condition of the loop. This is a serious programming error.
 Although loops typically iterate over only one variable, sometimes for loops need to work with multiple variables.

When we declare a variable inside a loop, the scope of that variable ends with the end of the loop statement. In other words, the scope of the loop variable is inside the loop, and it can not be accessed from outside the loop.
int w
// we can use x or w inside ()
for(int x = 0; x < 5; x = x + 1)
{
int y
// we can use x, y, w here
}
int z
// we can only use w, z here;
x and y are only visible in the scope of the loop.
Critical concepts to explore in Loop
 Break and Continue loop statements
 Two pointers and sliding window approach
 The idea of iterator in data structure
 Iteration vs. Recursion comparison
 Iterative problemsolving approaches
 Time complexity analysis of various loops
Coding problems to practice using loop
 Convert roman to integer
 Fizz Buzz Problem
 LookandSay Sequence
 Move zeroes to an end
 Merge two sorted array
 max and min of an array
 Print a given matrix in spiral form
 Rotate a matrix by 90 degrees
Enjoy learning, Enjoy coding, Enjoy algorithms!