BUILDING BLOCKS OF ALGORITHMS

(iii) Repetition: Iterative or repetitive execution of a sequence of actions, is the
basis of expressing long processes by comparatively small number of
instructions. As we deal with only finite processes, therefore, the repeated
execution of the sequence of actions, has to be terminated. The termination
may be achieved either through some condition Q or by stating in advance the
number of times the sequence is intended to be executed.

(a) When we intend to execute a sequence S of actions repeatedly, while
condition Q holds, the following notation may be used for the purpose:
While (Q) do begin S end;

Example: We are required to find out the sum (SUM) of first n natural
numbers. Let a variable x be used to store an integer less than or equal to n, then the algorithm for the purpose may be of the form:

algorithm Sum_First_N_1
begin
read (n); {assuming value of n is an integer ≥ 1}
x←1 ; SUM← 1;
while (x < n) do …………………………………… α )1(
begin
x ← x + 1;
SUM ← SUM + x
end; {of while loop}……………………………… β )1(
write (‘The sum of the first’, n, ‘natural numbers is’ SUM)
end. {of algorithm}

Explanation of the algorithm Sum_First_N_1:

Initially, an integer value of the variable n is read. Just to simplify the argument, we
assume that the integer n 1. The next two statements assign value 1 to each of the
variables x and SUM. Next, we come the execution of the while-loop. The while-loop extends from the statement ≥ α )1( to β )1( both inclusive. Whenever we enter the loop, the condition x<n is (always) tested. If the condition x<n is true then the whole of the remaining portion upto β (inclusive) is executed. However, if the condition is false then all the remaining statement of the while-loop, i.e., all statements upto and including (β 1)are skipped.

Therefore, as 1<3, therefore the condition x<n is true. Hence the following portion of
the while loop is executed:
begin

x←x+1;

SUM ← SUM+X;
end
and as a consequence of execution of this composite statement

the value of x becomes 1 and
and the value of SUM becomes 3

As soon as the word end is encountered by the meaning of the while-loop, the whole of the while-loop between α )1( and β )1( , (including α )1( and (β1)) is again
executed.
By our assumption n = 3 and it did not change since the initial assumption about n;
however, x has become 2. Therefore, x<n is again satisfied. Again the rest of the
while loop is executed. Because of the execution of the rest of the loop, x becomes 3 and SUM becomes the algorithm comes to the execution of first statement of whileloop, i.e., while (x<n) do, which tests whether x<n. At this stage x=3 and n=3.
Therefore, x<n is false. Therefore, all statement upto and including (β1) are x<n
skipped.
Then the algorithm executes the next statement, viz., write (‘The sum of the first’, n,
‘natural numbers is’, sum). As, at this stage, the value of SUM is 6, the following
statement is prompted, on the monitor:
The sum of the first 3 natural numbers is 6.
It may be noticed that in the statement write (‘ ‘, n, ‘ ’, SUM) the variables n and
SUM are not within the quotes and hence, the values of n and SUM viz 3 and 6 just
before the write statement are given as output,
Some variations of the ‘while…do’ notation, are used in different programming
languages. For example, if S is to be executed at least once, then the programming
language C uses the following statement:
Do S while (Q)
Here S is called the body of the ‘do. while’ loop. It may be noted that here S is not
surrounded by the brackets, viz., begin and end. It is because of the fact do and while enclose S.
Again consider the example given above, of finding out the sum of first n natural
numbers. The using ‘do … while’ statement, may be of the form:
The above instruction is denoted in the programming language Pascal by
Repeat S until (not Q)
Example Algorithm Sum_First_N_2

Begin {of algorithm}
read (n);

x←0 ; SUM← 0
do ( 2α
x ← x + 1
SUM← SUM + x

while (x < n) ………………. ( 2β )
end {of algorithm}.
If number n of the times S is to be executed is known in advance, the
following notation may be used:
for v varying from i to (i+n–1) do begin S end;