Algorithmic statements

Reading time5 min

In brief

Article summary

In this article, we present you the main constituents of an algorithm: statements, loops, and conditional statements. We also mention the risks of loops, and present you briefly a formal approach to make sure you do not have infinite loops.

Main takeaways

  • A statement is an atomic constituent of an algorithm.

  • Statements can be grouped in blocks of statements (or other blocks).

  • A loop (for or while) allows to execute a block of statements multiple times, until a condition is met.

  • A conditional statement (if) allows to execute or not a block of statements, based on a condition.

Article contents

1 — Simple statements

A statement is an atomic algorithmic instruction. Statements forming an algorithm are executed sequentially. Think of a cooking recipee. A statement could be for instance “add sugar” or “put into the oven”. Or, closer to what we need, a = 2 * b or print(x).

Several statements (and blocks) may be regrouped to form a block of statements. Blocks can then be executed or not based on some test, or run multiple times. Here are the main algorithmic structures:

2 — Conditions

Conditional statements (if) are used to split the sequential execution of the algorithm based on a Boolean condition. If this condition is evaluated to true, then a block of statements is executed. Otherwise, another one is executed, in the else part of the test.

​
# Set some variables
balance = 453.5
request = 60

# Beginning of the conditional statement
if balance - request >= 0:

    # This block of code is executed if the test is True
    print("Withdrawal request accepted")
    balance -= request

else:

    # This block of code is executed if the test is False
    print("Withdraw request rejected: balance too low")
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Set some variables
        double balance = 453.5;
        double request = 60;

        // Beginning of the conditional statement
        if (balance - request >= 0) {
            // This block of code is executed if the test is True
            System.out.println("Withdrawal request accepted");
            balance = balance - request;
        } else {
            // This block of code is executed if the test is False
            System.out.println("Withdraw request rejected: balance too low");
        }
    }
}
Information

The else part of the conditional statement is optional.

Also, several conditional statements can be nested. Some languages require to put the new test in the if or else section, but others provide a keyword for this. Here is a code corresponding to the first case:

​
# Set some variables
balance = 453.5
request = 60

# Beginning of the conditional statement
if balance - request >= 0:

    # Nested conditional statement
    if balance - request == 0:

        # This block of code is executed if the first test is True and the nested test is True
        print("Withdrawal request accepted")
        print("Bank account is now empty")
        balance -= request
    
    else:

        # This block of code is executed if the first test is True and the nested test is False
        print("Withdrawal request accepted")
        balance -= request

else:

    # This block of code is executed if the first test is False
    print("Withdraw request rejected: balance too low")
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Set some variables
        double balance = 453.5;
        double request = 60;
        // Beginning of the conditional statement
        if (balance - request > 0) {
            // Nested conditional statement
            if (balance - request == 0) {
                // This block of code is executed if the first test is True and the nested test is True
                System.out.println("Withdrawal request accepted")
                System.out.println("Bank account is now empty")
                balance = balance - request;
            } else {
                // This block of code is executed if the first test is True and the nested test is False
                System.out.println("Withdrawal request accepted");
                balance = balance - request;
            }
        } else {
            // This block of code is executed if the first test is False
            System.out.println("Withdraw request rejected: balance too low");
        }
    }

}

And one with that particular keyword:

​
# Set some variables
balance = 453.5
request = 60

# Beginning of the conditional statement
if balance - request > 0:

    # This block of code is executed if the test is True
    print("Withdrawal request accepted")
    balance -= request

elif balance - request == 0:

    # This block of code is executed if the first test is False and the second test is True
    print("Withdrawal request accepted")
    print("Bank account is now empty")
    balance -= request

else:

    # This block of code is executed if both tests are False
    print("Withdraw request rejected: balance too low")
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Set some variables
        double balance = 453.5;
        double request = 60;
        // Beginning of the conditional statement
        if (balance - request > 0) {
            // This block of code is executed if the test is True
            System.out.println("Withdrawal request accepted");
            balance = balance - request;
        } else if (balance - request == 0) {
            // This block of code is executed if the first test is False and the second test is True
            System.out.println("Withdrawal request accepted")
            System.out.println("Bank account is now empty")
            balance = balance - request;
        } else {
            // This block of code is executed if both tests are False
            System.out.println("Withdraw request rejected: balance too low");
        }
    }

}

3 — Loops

Many solutions to algorithmic problems rely on the repetition of a block of statements until an expected state is reached. Iterating on a block of statements is done using loops that make it possible to define cycles in the execution flow of an algorithm. There are two types of loops:

  • Bounded loops
  • Unbounded loops.

Bounded loops (or for loops) are used when the number of iterations to perform is known a priori. They perform a fixed number of iterations.

​
# Initialize a few variables
v = 1
n = 10
print("v =", v)

# A loop that will iterate 10 times
for i in range(n):
    v /= 2
    print("v =", v)
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Initialize a few variables
        double v = 1;
        int n = 10;
        System.out.println("v = " + v);

        // A loop that will iterate 10 times
        for (int i = 0; i < n; i++) {
            v = v / 2;
            System.out.println("v = " + v);
        }
    }

}

Unbounded loops (or while loops) will iterate until a condition is reached. As you will see below, there is therefore a risk of infinite loop if you are not careful. Here is an code similar to the one above that uses an unbounded loop to check the value of v to stop:

​
# Initialize a few variables
v = 1
print("v =", v)

# A loop that will iterate until v is low enough
while v > 0.000001:
    v /= 2
    print("v =", v)
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Initialize a few variables
        double v = 1;
        System.out.println("v = " + v);

        // A loop that will iterate until v is low enough
        while (v > 0.000001) {
            v = v / 2;
            System.out.println("v = " + v);
        }
    }

}

Unbounded loops are universal, meaning that any iterative problem can be solved using unbounded loops, whereas bounded loops require that the number of loops to be performed is known in advance.

To go further

4 — Loop correctness

Loops often constitute core elements of algorithms. Testing loops is not enough to ensure that they will always produce the expected results. Formal languages and methods, as the Hoare logic, have been conceived to prove the correct ending of algorithms. It is proposed hereafter to focus on proving the correctness of loops using mathematical induction.

The notion of invariant is used to prove by induction that a loop effectively reaches an expected state from an initial state. This expected state is defined by the values taken by the different variables involved in the algorithm. Invariants are used to prove the correcteness of a loop.

An invariant is a Boolean condition that is true in the initial state, i.e., before the first round of the loop, and that remains true at the end of each iteration.

Loops also involve a variant that obviously describes the constituent of the algorithm that evolves during the iteration. The variant is often defined by means of a natural integer materializing the progression of the iteration towards the expected result. Variants are used to prove the termination of a loop.

Example

Consider a list of characters named s (of length N), and a loop whose aim is to determine the number of occurences of the symbol assigned to variable v. The number of occurences is stored in a variable named nb_occ.

The variant part of the interation is defined by:

  • A natural i indicating the position of the letter in s to analyze (to check if it is equal to v). i is initialized with 0.
  • Another natural, nb_occ, initialized with 0.

A possible invariant is:

  • “nb_occ contains the number of occurrences of v found in the prefix of s up to position i (excluded)”.

Here is a proposition of an algorithm to solve this problem:

​
# A few variables
s = ['B', 'o', 'n', 'j', 'o', 'u', 'r', ' ', 'c', 'h', 'e', 'r', '.', 'e', '.', 's', ' ', 'é', 't', 'u', 'd', 'i', 'a', 'n', 't', '.', 'e', '.', 's']
v = 'e'
i = 0
nb_occ = 0

# Loop over the list
while i < len(s):
    if s[i] == v:
        nb_occ += 1
    i += 1

# Done
print("The number of occurrences of", v, "=", nb_occ)
/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // A few variables
        char s[] = {'B', 'o', 'n', 'j', 'o', 'u', 'r', ' ', 'c', 'h', 'e', 'r', '.', 'e', '.', 's', ' ', 'é', 't', 'u', 'd', 'i', 'a', 'n', 't', '.', 'e', '.', 's'};
        char v = 'e';
        int i = 0;
        int nb_occ = 0;

        // Loop over the list
        while (i < s.length) {
            if (s[i] == v) {
                nb_occ += 1;
            }
            i += 1;
        }

        // Done
        System.out.println("The number of occurrences of " + v + " = " + nb_occ);
    }

}

To prove the correctness of this iteration, the veracity of the invariant must first be checked at the initialisation, i.e., before the first round of the iteration.

  • After the initialization, the prefix of s up to position i = 0 is an empty string, meaning that 0 occurences of v has been found so far. nb_occ being initialised with 0, the invariant is satisfied before the first round of the loop.

    Then, considering that the invariant is true for a given value of the variant i in interval $[0, N-1[ $, one now has to show that it will also be true for i + 1.

  • Since the invariant is true for i, nb_occ contains the number of occurrences of v in the prefix of s up to position i - 1. For i + 1, the character at position i is compared to v (condition of the if ... then ... statement), and if they match then nb_occ is incremented. In any case, i is incremented. So, at the end of an iteration, nb_occ has been incremented only if a new occurrence of v has been found at position i - 1, confirming that the invariant remains true at the end of an interation step.

The loop ends when i == N and nb_occ contains the number of occurrences of v found in the prefix of s up to position N excluded, which corresponds to the entirety of s.

So, at the end of the loop, nb_occ contains the expected result.

To go beyond