Algorithmic statements

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");
        }
    }
}

# 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");
        }
    }

}

# 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.

# 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 go beyond

• Program correctness using induction.

  A few more examples on how to prove program correctness with induction.