CS13002 Programming and Data Structures

CS13002 Programming and Data Structures

Spring semester

Loops and iteration

This is the first time we are going to make an attempt to move backward in a program. Loops make this backward movement feasible in a controlled manner. This control is imparted by logical conditions.
Many problem-solving strategies involve repetitive steps. For example, suppose we want to compute the sum of n numbers. A specific instance of this problem is the computation of the harmonic number:
   H_n = 1/1 + 1/2 + 1/3 + ... + 1/n.
A reasonable strategy to solve this problem is to start with a sum initialized to zero and then let each 1/i be added to the sum. When all of the n summands are added, the number accumulated in the sum is the desired output. Here the repetitive part is the addition of the next number to the current sum. So there should be a way to identify the "next" number. Moreover, when there are no more (next) numbers, the repetitive addition should stop. Here is a high-level description of this process:
   Initialize sum to 0.
   for each i in the set {1,2,...,n} add 1/i to sum.
   Report the accumulated sum as the output value.
Here i identifies the "next" number and when all of the n possible values of i have been tried out, the repetitive addition process should stop.

Mathematical induction

Let us formalize the above notion of repetitive calculation. The following sets occur frequently in the study of computer science. So let us designate them by some special symbols.

Symbol Set Description
N {1,2,3,4,...} The set of natural numbers (i.e., positive integers)
N₀ {0,1,2,3,...} The set of non-negative integers
Z {...,-3,-2,-1,0,1,2,3,...} The set of integers

Theorem: [Principle of mathematical induction]

Let S be a subset of N with the following properties:
        (1) 1 is in S.
        (2) Whenever n is in S, so also is n+1.
Then S = N.

A similar theorem holds for the set N₀:
Theorem: [Principle of mathematical induction]

Let S be a subset of N₀ with the following properties:
        (1) 0 is in S.
        (2) Whenever n is in S, so also is n+1.
Then S = N₀.

The principle of mathematical induction can be stated in various equivalent forms. The following is one such equivalent statement.
Theorem: [Principle of strong mathematical induction]

Let S be a subset of N with the following properties:
        (1) 1 is in S.
        (2) Whenever 1,2,...,n are in S, so also is n+1.
Then S = N.

For N₀ this can be stated as:
Theorem: [Principle of strong mathematical induction]

Let S be a subset of N₀ with the following properties:
        (1) 0 is in S.
        (2) Whenever 0,1,2,...,n are in S, so also is n+1.
Then S = N₀.

Let us now see how we can exploit these principles for designing iterative algorithms. First look at the the computation of harmonic numbers. For the sake of simplicity let us also define:
   H₀ = 0.
Let S denote the set of all non-negative integers for which H_n can be computed. I will show that S = N₀. First, H₀ is equal to the constant 0 and so can be computed; so 0 is in S. Now suppose that H_n can be computed for some n>=0, i.e., n is in S. It is easy to see that
   H_n+1 = H_n + 1/(n+1).
But then since 1/(n+1) is also computable, adding this quantity to H_n gives us a way to compute H_n+1, i.e., n+1 is in S too. Hence by the principle of mathematical induction S = N₀.
This argument not only establishes that H_n can be computed for all non-negative n, but also suggests a way to compute H_n. Here is the algorithm:
   Set i = 0 and H₀ = 0.
   For i = 1,2,3,...,n in that order
      compute H_i = H_i-1 + 1/i.
We will shortly see how this English description can be translated to a C program. For the time being let us concentrate on some other examples.
The greatest common divisor gcd(a,b) of two non-negative integers (not both 0) is defined as the largest natural number of which both a and b are integral multiples. The standard gcd algorithm taught in schools is based on successive Euclidean division. Let us try to render it as a sequence of repetitive computations. For the sake of simplicity, we assume that whenever we write gcd(a,b) we mean a>=b.
The first step is to show that gcd(a,b) is computable for all a>=1 and for all b in the range 0<=b<=a. We proceed by induction on a. If a=1, we must have b=0 or b=1. Now both gcd(1,0) and gcd(1,1) equal the constant 1. For the inductive step assume that gcd(a',b') is computable whenever a'<a, and that we want to compute gcd(a,b). We use the following theorem:
Theorem: [Euclidean gcd theorem]
Let a,b be positive integers and r = a rem b. Then gcd(a,b) = gcd(b,r).
Let us now come back to the inductive step. If a is an integral multiple of b, we have r=0, and so by the theorem gcd(a,b)=gcd(b,0)=b. If a is not an integral multiple of b, we cannot have a=b, i.e., now a>b. By the induction hypothesis gcd(b,r) is computable. Also the remainder r is computable from a and b. Therefore, gcd(a,b) is also computable.
This proof also leads to the following iterative algorithm:
   As long as b is not equal to 0 do the following:
      Compute the remainder r = a rem b.
      Replace a by b and b by r.
   Report a as the desired gcd.
Recursive definitions

A sequence a_n for all n in N (or N₀) can often be inductively (also called recursively) defined. For example, the sequence of harmonic numbers is defined as:
   H₀ = 0,
   H_n = H_n-1 + (1/n) for n>=1.
The sequence a_n = n² can be recursively defined as:
   a₀ = 0,
   a_n = a_n-1 + 2n - 1 for n>=1.
Also recall the definition of Fibonacci numbers:
   F₀ = 0,
   F₁ = 1,
   F_n = F_n-1 + F_n-2 for n>=2.
In all these cases the recursive definition provides a way to compute an element in the sequence from one or more elements that occur earlier in the sequence. The basis cases specify the terminal conditions, where constant values are to be used for the initial elements of the sequence.
More complicated entities may also be defined recursively. For example, suppose we want to obtain the list of all permutations of the natural numbers 1,2,...,n. If n=1, the list consists of a single element. For n>=2, we inductively compute the list of permutations of 1,2,...,n-1. Then for each permutation in the list we insert n in any one of the n allowed positions. One can easily check that in this way we can generate all the permutations of 1,2,...,n with each such permutation generated exactly once.
Induction proves to be a useful methodology for attacking problems. In the first place, it is procedural, i.e., it often leads to good algorithms for computing recursively defined objects. Second, the idea of reduction of a problem into one or more smaller problems and then combining the solutions of the subproblems to obtain the solution of the original problem turns out to be extremely useful for designing algorithms. We will come back again to a discussion of recursion in connection with functions.

Loops

It is high time now that we concentrate on the realization of repetitive structures in C. In the C terminology these are called loops.
Pre-test and post-test loops

Loops can be broadly classified in two categories based on the location where the condition for looping back is checked.
In a pre-test loop the condition for entering the body of the loop is checked at the beginning (top) of the loop. If the condition is satisfied, execution enters the body and proceeds sequentially. After the entire body is executed, control comes back unconditionally to the top of the loop. Meanwhile, the body might have changed the world in a way so as to affect the continuation condition. If it is still satisfied, the loop is entered once more, and the body is again executed and control again comes back to the top of the loop. If the condition at the top is not satisfied, the loop body is ignored and the control of execution goes to the area after the end of the loop.

Figure: Pre-test loop
In a post-test loop, on the other hand, the control of execution enters the loop body unconditionally. After the entire body is executed, the loop condition is checked. If it is satisfied, control goes back to the top of the loop, the body is again executed and the continuation condition is again checked. This process is repeated until the continuation condition becomes false. In that case, control leaves the loop and proceeds further down the code.

Figure: Post-test loop
It is important to note that for a post-test loop the loop body is executed at least once, since control enters the body unconditionally. On the other hand, in a pre-test loop the loop body need not be executed at all. If the continuation condition is false initially, the entire loop is ignored.
while loops

The pre-test loop of the above figure can be rendered in C as follows:
   while (the continuation condition is true) {
      execute loop body;
   }
If the loop body consists of a single statement, the braces may be omitted.
Example: As a specific example of a while loop, let us implement the gcd algorithm using repeated division.
   while (b > 0) {
      r = a % b;     /* Compute the next remainder */
      a = b;         /* Replace a by b */
      b = r;         /* Replace b by r */
   }
   printf("gcd = %d\n",a);
Animation example : while loop

Interactive animation : while loop

Interactive animation : gcd

Interactive animation : Euclidean gcd

Example: Here is how the n-th harmonic number may be computed using a while loop. Note that H_i can be generated from H_i-1 and i. So it is not necessary to store all the values H₀,H₁,...,H_i-1. Remembering only the previous harmonic number suffices.
   float i, H;
   unsigned int n;

   ...

   i = 0;
   H = 0;
   while (i < n) {
      ++i;          /* Increment i */
      H += 1.0/i;   /* Update the harmonic number accordingly */
   }
   printf("H(%d) = %f\n", n, H);
Example: Finally, let us look at the computation of Fibonacci numbers using while loops.
   i = 1;    /* Initialize i to 1 */
   F = 1;    /* Initialize F_i */
   p1 = 0;   /* Initialize F_i-1 */
   while (i < n) {
      ++i;          /* Increment i */
      p2 = p1;      /* The old F_i-1 now becomes F_i-2 */
      p1 = F;       /* The old F_i now becomes F_i-1 */
      F = p1 + p2;  /* Compute F_i from F_i-1 and F_i-2 */
   }
   printf("F(%d) = %d", n, F);
do-while loops

The do-while loop of C is a post-test loop. It has the following syntax:
   do {
      execute loop body;
   } while (continuation condition is true);
Example: Harmonic numbers can be computed using the do-while loop as:
   float i, H;
   unsigned int n;

   ...

   i = 0;
   H = 0;
   do {
      ++i;          /* Increment i */
      H += 1.0/i;   /* Update the harmonic number accordingly */
   } while (i < n);
   printf("H(%d) = %f\n", n, H);
Example: The following loop computes the gcd of two integers a,b with 1<=b<=a.
   do {
      r = a % b;     /* Compute the next remainder */
      a = b;         /* Replace a by b */
      b = r;         /* Replace b by r */
   } while (b > 0);
   printf("gcd = %d\n",a);
Example: Finally, here is an implementation of the computation of Fibonacci numbers F_i for i>=2.
   i = 1;    /* Initialize i to 1 */
   F = 1;    /* Initialize F_i */
   p1 = 0;   /* Initialize F_i-1 */
   do {
      ++i;          /* Increment i */
      p2 = p1;      /* The old F_i-1 now becomes F_i-2 */
      p1 = F;       /* The old F_i now becomes F_i-1 */
      F = p1 + p2;  /* Compute F_i from F_i-1 and F_i-2 */
   } while (i < n);
   printf("F(%d) = %d", n, F);
Animation example : do-while loop

Interactive animation : do-while loop

for loops

These are pre-test loops and have the following syntax:
   for ( initialize loop; continuation condition ; loop increment ) {
      execute loop body;
   }
Here the loop initialization step consists of a set of book-keeping task that need be carried out before entering the loop, and the loop increment step refers to a set of tasks carried out at the end of the loop body just before the continuation condition is checked. The for loop can be equivalently described in terms of the following while loop:
   initialize loop;
   while (continuation condition is true) {
      execute loop body;
      loop increment;
   }
Example: One can compute gcds using for loops as follows:
   for ( ; b > 0 ; ) {
      r = a % b;     /* Compute the next remainder */
      a = b;         /* Replace a by b */
      b = r;         /* Replace b by r */
   }
Here the initialization and increment steps are empty.
Example: Computation of harmonic numbers using for loops is quite simple:
   H = 0;
   for (i=1; i<=n; ++i) H += 1.0/i;
   printf("H(%d) = %f\n", n, H);
Example: If more than one statements need be executed during the initialization or increment step, they should be separated by commas, since semi-colons indicate separation of the three parts of the loop control area.
The Fibonacci computation may have the following form with for loops. We assume that n>=2.
   for ( i = 2, p1 = 1, p2 = 0; i <= n; ++i , p2 = p1 , p1 = F ) 
      F = p1 + p2;  /* Compute F_i from F_i-1 and F_i-2 */
   printf("F(%d) = %d", n, F);
Example: The following animation demonstrates an iterative computation of the sequence 1²+2²+...+n².

Animation example : for loop

Interactive animation : for loop

Interactive animation : computation of Fibonacci numbers

Example: The following animation iteratively assigns values to the elements of an array. The i-th location receives the value (i+1)².

Animation example : for loop with arrays

Example: [Linear search]
Given an array of n elements A[0],A[1],...,A[n-1] and an element x, we want to find if x is present in the array, i.e., if x = A[i] for some i. This is the famous search problem. One obvious strategy is to compare x successively with A[0],A[1],A[2],... The algorithm stops as soon as a match is found or the array gets exhausted.

Animation example : linear search

Interactive animation : linear search

The code for linear search is given below:
   found = 0;
   for (i=0; (!found)&&(i<n); ++i) {
      if (A[i] == x) {
         printf("Match found\n");
         found = 1;
      }
   }
   if (!found) printf("No match found\n");
Example: [Binary search]
Now assume that the array A is sorted, i.e., A[0] <= A[1] <= ... <= A[n-1]. First we compare the element x with the array element A[(n-1)/2]. If x > A[(n-1)/2], then x cannot be found in the first half of the array. On the other hand, if x <= A[(n-1)/2], there is no need to search x in the second half of the array. Thus by a single comparison we discard one half of the array. We then repeat the process, every time discarding half of the remaining part of the array. Eventually, we reduce the search to a single array element and check whether x equals this element.

Animation example : binary search

Interactive animation : binary search

Here is how we can translate the binary search algorithm in C:
   L = 0; R = n-1;
   while (L < R) {
      M = (L + R) / 2;
      if (x > A[M]) L = M+1; else R = M;
   }
   if (A[L] == x) printf("Match found\n");
   else printf("Match not found\n");
Loop invariants

For verifying the correctness of loops one often uses the concept of loop invariance. A loop invariant refers to a statement that is true at all instants when the loop condition is checked. It may be expressed in terms of one or more variables controlling the flow of the loop.
Example: Consider the while loop implementation of the computation of H_n.
   i = 0;
   H = 0;
   while (i < n) {
      ++i;          /* Incremet i */
      H += 1.0/i;   /* Update the harmonic number accordingly */
   }
Here the loop invariant is the statement "H stores the value H_i for all i=0,1,2,...,n". The correctness of this statement can be proved using induction on i. It is initially true (H₀=0). Now suppose it is true for a particular i < n. As the loop body is executed the value of i changes to i+1 and that of H changes to H_i+1/(i+1)=H_i+1. The loop terminates when i equals n. By the loop invariance property H then stores the value H_n. This is precisely what we wanted to compute.
Example: Next look at the do-while implementation of Fibonacci computation.
   i = 1;    /* Initialize i to 1 */
   F = 1;    /* Initialize F_i */
   p1 = 0;   /* Initialize F_i-1 */
   do {
      ++i;          /* Increment i */
      p2 = p1;      /* The old F_i-1 now becomes F_i-2 */
      p1 = F;       /* The old F_i now becomes F_i-1 */
      F = p1 + p2;  /* Compute F_i from F_i-1 and F_i-2 */
   } while (i < n);
It is easy to check that an invariant for this loop is the statement "F holds the value F_i and p1 the value F_i-1" and is true for i=1,2,...,n. The loop terminates for i=n, and in that case F stores F_n as desired.
Example: Here is a new example. Suppose we want to compute the maximum of n positive integers stored in an array A.
   max = A[0];
   for (i=1; i<n; ++i) {
      if (A[i] > max) max = A[i];
   }
A loop invariant here is "max stores the maximum value among the integers A[0],A[1],...,A[i-1]" and is true for all i=1,2,...,n.
Example: Let us now come to a really non-trivial example of loop invariance.
Theorem: Let a,b be positive integers and d = gcd(a,b). Then there exist integers u,v with the property that ua + vb = d.
Computation of the gcd d along with the multipliers u,v is called the extended gcd computation. The following algorithm does that.
   /* Initialize */
   r2 = a; u2 = 1; v2 = 0;  /* Previous-to-previous values */
   r1 = b; u1 = 0; v1 = 1;  /* Previous values */

   /* Extended gcd loop */
   while (r1 > 0) {
      /* Compute values for the current iteration */
      q = r2 / r1;       /* Compute the next quotient */
      r = r2 - q * r1;   /* Compute the next remainder */
      u = u2 - q * u1;   /* Identically compute the next u value */
      v = v2 - q * v1;   /* Identically compute the next v value */

      /* Prepare for the next iteration */
      r2 = r1; u2 = u1; v2 = v1;  /* Let the previous-to-previous values be the previous values */
      r1 = r; u1 = u; v2 = v;     /* Let the previous values be the current values */
   }

   printf("gcd(a,b) = %d = (%d) * a + (%d) * b\n", r2, u2, v2);
Interactive animation : extended Euclidean gcd

It is not at all clear that this algorithm works correctly. The correctness can be established from the following invariance property:
Claim: Whenever the continuation condition for the above loop is checked, we have:
   gcd(r2,r1) = gcd(a,b),      (1)
   u2 * a + v2 * b = r2,       (2)
   u1 * a + v1 * b = r1.       (3)
Proof The three conditions are obviously true at the beginning of the first iteration; this is how the values are initialized. Now suppose that the relations hold for certain iteration with r1 > 0. The loop body is then executed. First, the quotient q and the remainder r of Euclidean division of r2 by r1 is computed. By Euclid's gcd theorem
   gcd(r1,r) = gcd(r2,r1) = gcd(a,b).
Moreover,
   u = u2 - q * u1, and v = v2 - q * v1,
and so
     u * a + v * b
   = (u2 - q * u1) * a + (v2 - q * v1) * b
   = (u2 * a + v2 * b) - q * (u1 * a + v1 * b)
   = r2 - q * r1
   = r.
Thus the three equations (1)-(3) continue to be satisfied for the new r,u,v values. QED
The loop terminates when r1 becomes 0. In that case gcd(a,b) = gcd(r2,r1) = gcd(r2,0) = r2 = u2 * a + v2 * b, and, therefore, r2,u2,v2 constitute a desired set of values for the extended gcd.
Let us look at the trace of the values stored in different variables for a sample run with a=78 and b=21.

Iteration No r2 r1 u2 u1 v2 v1 q r u v u2*a+v2*b
Before loop 78 21 1 0 0 1 - - - - 78
1 78
21 21
15 1
0 0
1 0
1 1
-3 3
3 15
15 1
1 -3
-3 78
21
2 21
15 15
6 0
1 1
-1 1
-3 3
4 1
1 6
6 -1
-1 4
4 21
15
3 15
6 6
3 1
-1 -1
3 -3
4 4
-11 2
2 3
3 3
3 -11
-11 15
6
4 6
3 3
0 -1
3 3
-7 4
-11 -11
26 2
2 0
0 -7
-7 26
26 6
3

gcd(78,21) = 3 = (3) * 78 + (-11) * 21

Nested loops

One or more loops can be nested inside another loop. In that case the inner loops usually have continuation conditions dependent on variables different from the variable(s) governing the continuation of the outer loop. The programmer should be sufficiently careful so as not to do something silly inside the inner loops, that affects the behavior of the outer loop.
Example: [Bubble sort]
Suppose you have an array A of n elements (say, integers). They are stored in the array locations A[0],A[1],...,A[n-1]. We want to rearrange these integers in such a way that after the rearrangement we have
   A[0] <= A[1] <= A[2] <= ... <= A[n-1].
Such an array is called a sorted array and the process of making the array sorted is refered to as sorting. Sorting is a basic and fundamental computational problem. There are several algorithms proposed for sorting. For the time being, let us look at an algorithm known as bubble sort.

Animation example : bubble sort

Interactive animation : bubble sort

The bubble sort algorithm can be implemented using a singly nested loop as follows:
   for (i=n-2; i>=0; --i) {    /* Attempt to bubble till the value of i */
      for (j=0; j<=i; ++j) {   /* Run j from 0 to the current upper bound i */
         if (A[j] > A[j+1]) {  /* Two consecutive elements are in the opposite order */
                               /* Swap A[j] and A[j+1] */
            t = A[j];          /* Store A[j] in a temporary variable t */
            A[j] = A[j+1];     /* Change A[j] to A[j+1] */
            A[j+1] = t;        /* Change A[j+1] to the old value of A[j] stored in t */
         }
      }
   }
Example: [Selection sort]
The working of the selection sort is somewhat similar to that of bubble sort. Here the outer loop runs over i ranging from n-1 down to 1. For a given i, the largest element in the subarray A[0],A[1],...,A[i] is found out and is swapped with the element A[i]. Thus during the first iteration of the outer loop A[n-1] receives the largest element in the array, in the second iteration A[n-2] receives the second largest element, and so on.

Animation example : selection sort

Interactive animation : selection sort

The code for selection sort follows:
   for (i=n-1; i>=1; --i) {
      /* First find the maximum element of A[0],A[1],...,A[i] */
      /* Initialize maximum entry to be the leftmost one */
      maxidx = 0;
      max = A[0];
      /* Now search for a potentially bigger maximum */
      for (j=1; j<=i; ++j) {
         if (A[j] > max) {  /* An element bigger that the current maximum is located */
            /* Adjust the maximum entry */
            maxidx = j;
            max = A[j];
         }
      }
      /* Swap A[i] with the maximum element */
      A[maxidx] = A[i];  /* Store the last element at index maxidx */
      A[i] = max;        /* Store the maximum at the last index */
   }
Example: [Insertion sort]
Here is yet another sorting algorithm that uses nested loops. Here the outer loop runs over a variable i ranging from 1 to n-1. For a particular i, the portion A[0],A[1],...,A[i-1] is already sorted. Then the element A[i] is considered and is inserted at the appropriate position in the sorted list A[0],A[1],...,A[i-1]. That will make a bigger sorted list A[0],A[1],...,A[i]. When the loop body finishes execution with i=n, the entire array is sorted.

Animation example : insertion sort

Interactive animation : insertion sort

Here is the code for insertion sort.
   for (i=1; i<n; ++i) {        /* Consider A[i] */
      /* Search for the correct insertion location of A[i] */
      t = A[i];                 /* Store A[i] in a temporary variable */
      j = 0;                    /* Initialize search location */
      while (t > A[j]) ++j;     /* Skip smaller entries */
      /* Here j holds the desired insertion location */

      /* Shift forward the remaining entries each by one location */
      for (k=i-1; k>=j; --k) A[k+1] = A[k];

      /* Finally insert the old A[i] at the j-th location */
      A[j] = t;
   }
Flow control inside loops

The continuation condition dictates whether the loop body is to be repeated or skipped. There are some constructs by which this natural flow can be altered.
The break statement

A loop may be forcibly broken from inside irrespective of whether the continuation condition is satisfied or not. This is achieved by the break statement.
Example: Let us write the gcd algorithm with explicit break statement. Here we make the loop an infinite one. The check whether b equals 0 is carried out inside the loop. If the check succeeds, the loop is broken explicitly by a break statement.
   while (1) {
      if (b == 0) break;
      r = a % b;
      a = b;
      b = r;
   }
   printf("gcd = %d\n", a);
Note that any loop can be implemented as an infinite loop with an explicit break. The do-while loop
   do {
      execute loop body;
   } while (continuation condition is true);
is equivalent to
   do {
      execute loop body;
      if (continuation condition is false) break;
   } while (1);
and also to
   while (1) {
      execute loop body;
      if (continuation condition is false) break;
   }
Interactive animation : for loop with break

In case of nested loops, a break statement causes the innermost loop (in which the statement is executed) to be broken. As a toy example, suppose that we want to compute the sum of gcds of all pairs (a,b) with 1<=a<=b<=20. Here is an implementation with explicit break statements.
   /* Initialize sum */
   sum = 0;

   for (i=1; i<=20; ++i) {
      for (j=i; j<=20; ++j) {
         /* Now we plan to compute gcd(j,i) */
         /* But we must not disturb the loop variables */
         /* So we copy j and i to temporary variables a and b and change those copies */
         a = j; b = i;

         /* The Euclidean gcd loop */
         while (1) {
            if (b == 0) break; /* gcd computation is over, so break the while loop */
            r = a % b;
            a = b;
            b = r;
         }

         /* When the while loop is broken, a contains gcd(j,i). Add it to the accumulating sum. */
         sum += a;
      }
   }
   printf("The desired sum = %d\n", sum);
Next follows a more obfuscating implementation of the same algorithm. Here all the loops are broken with explicit break statements. Moreover, the break statements occur in the middle of the loops. Finally, the gcd loop is rewritten so that we can break as soon as we find a zero remainder. In that case, b holds the desired gcd.
   sum = 0;                    /* Initialize sum to 0 */
   i = 0;                      /* Initialize the outer loop variable */
   while (1 != 0) {            /* This condition is always true */
      j = ++i;                 /* Increment i and assign the incremented value to j */
      if (j == 21) break;      /* Break the outermost loop */
      while (3.1416 > 0) {     /* This condition is always true */
         a = j; b = i;         /* Copy j and i to temporary variables */
         while ('A') {         /* This condition is again always true, since 'A' = 65 */
            r = a % b;         /* Compute next remainder */
            if (!r) break;     /* Break the innermost loop */
            a = b;             /* Adjust a and b and */
            b = r;             /* prepare for the next iteration */
         }                     /* End of innermost loop */
         sum += b;             /* Add gcd(j,i) to the accumulating sum */
         if (j == 20) break;   /* Break the intermediate loop */
         ++j;                  /* Prepare for the next value of j */
      }                        /* End of intermediate loop */
   }                           /* End of outermost loop */
   printf("The desired sum = %d\n", sum);
Well then, is it a good style to write programs this way? Certainly no! This makes your code quite unreadable to (and hence unusable by) others. Even if some code is meant for your personal consumption only, debugging it may cause you enough headache, in particular, when you are already pretty tired or hungry and plan to finish the day's programming as early as possible.
Programming is fun anyway. For the kick you may at your leisure time make attempts to write and/or understand obfuscated codes. So then, what does the following program print (as a function of n)?
   #include <stdio.h>

   main ()
   {
      unsigned int n, i, j, s;

      printf("Enter a positive integer : ");
      scanf("%d",&n);
      s = 0x00000041 ^ (unsigned int)'A';
      while (i = --n) while (j = --i) while (--j) ++s;
      printf("s = %d\n", s);
   }
The continue statement

The continue statement also affects the normal execution of a loop. It does not cause the loop to terminate, but throws the control to the top of the loop ignoring the remaining part of the loop body for the current iteration.
Example: Suppose we want to print the integers 1,2,...,100 neatly with 10 integers printed in a line. Here is how this can be done:
   for (i=1; i<=100; ++i) {
      printf("%4d",i);
      if (i%10 != 0) continue;
      printf("\n");
   }
Here if i is a multiple of 10, the new line character is printed. Otherwise the continue statement lets the control flow reach the top of the loop, i.e., to the loop increment area where the variable i is incremented. The same effect can be realized by the following while loop:
   i = 0;
   while (i < 100) {
      ++i;
      printf("%4d",i);
      if (i%10 != 0) continue;
      printf("\n");
   }
Interactive animation : for loop with continue
Course home