A Painless Intro to Pseudocode and Control Flow

Finding the minimum of two numbers

We will soon return to the problem of computing a GCD; for now, we will start to explain how we will program a computer. Dozens of programming languages have been developed to allow us to convert ideas into computer instructions, and each language has its own quirks that take time to learn. We want to get started explaining computational ideas as quickly as we can, and so we will place learning a specific language on hold for now. Instead, we will use a general way of describing algorithms called pseudocode that avoids getting mired in the details of a specific language.

We will illustrate pseudocode with a simple example in the form of the following computational problem.

You might think that this problem cannot possibly hold any interest  —  we simply need to look at the two numbers and see which one is smaller! Yet we will soon see that even finding the minimum value of a collection of numbers can indicate important computational principles.

We will think of an algorithm solving a computational problem as a function that takes in the input variables specified by the problem, processes these variables in some way, and then returns the output solving the problem. This notion of a function parallels the mathematical view of a function, which is commonly taught as a “machine” that takes one or more variables as input and maps the input variables to one or more output values. For example, the mathematical function f(x,y) = (x + 3, y − 4, x · y) takes two input variables and returns a triple of values. In the case of the Minimum of Two Numbers Problem, we will call our function Min2(), and it should take as input the two parameters a and b.

A seminal tool in programming is the ability to check a condition and branch a computer program into different possibilities based on this condition. When computing the minimum of a and b, we would like to check if a is smaller, in which case a is our minimum, and the function Min2() should return its value; otherwise, Min2() should return the value of b.

We can represent such a test in pseudocode by an if statement, in which we take one action if a statement is true and another action if it is not. Below is pseudocode for Min2(), which includes our if statement.

Min2(a, b)
    if a < b
        return a
    else
        return b

The first line of Min2() names the function and names the input variables. The second line tests if a is smaller than b. If this is true, then the program enters line 3 and returns the value of a. An important point is that the function will now terminate, as a function ends when it encounters a return statement. On the other hand, if a is not smaller than b, then the function does not execute line 3 but instead continues to line 4, where the else indicates that we should enter the indented line following else. Since a is not smaller than b, we know that a is greater than or equal to b, and so we can safely return the value of b (and halt the program).

The if statement in Min2() exemplifies a common if statement. The following hypothetical function first executes instructions A (which may contain one or many lines). If condition X is true, then the function executes instructions Y (called the if block); if the function doesn’t encounter a return statement, then it continues onward to execute instructions B. On the other hand, if condition X is false, then the function executes instructions Z (called the else block); if it does not encounter a return statement in those instructions, then it executes instructions B.

SomeFunction(parameters)
    execute instructions A
    if condition X is true
        execute instructions Y
    else
        execute instructions Z
    execute instructions B

Although Min2() is a short function, it allows us to introduce control flow, or the sequence of steps that are taken when going through a function. Understanding control flow is central to a mastery of computer programming for two reasons. First, a computer program can only execute one instruction at a time (for now). Second, the control flow of a function implies a unique sequence of instructions for a given choice of parameters, which is critical because a computer needs precisely defined instructions to complete tasks.

You may be curious why certain words are typeset in bold in pseudocode. These words are called keywords, and they have reserved meanings in most programming languages. For example, a programming language would never let us use the word if to represent a variable, or return as a function name.

Subroutines: functions as building blocks

We will now tweak our ongoing problem by adding just a single input variable. Before reading on, try writing a function in pseudocode to solve it!

We solve the Minimum of Three Numbers Problem below using a function Min3(). If the control flow of this function is not yet clear, don’t worry, as  we will walk through it line by line.

Min3(a, b, c)
    if a < b
        if a < c
            return a
        else
            return c
    else
        if b < c
            return b
        else
            return c

After line 1 names the function and specifies the three input variables, line 2 contains an if statement testing whether a is smaller than b.

If a is smaller than b, then we can immediately deduce that b cannot be the minimum of the three parameters. As a result, we know that whichever of a and c is smaller must be our desired minimum. Lines 3–6 of Min3() contain the if block; in this block, we check which of a and c is smaller and return its value:

        if a < c
            return a
        else
            return c

These lines constitute a nested if statement within an if block in the Min3() function. This example indicates how powerful if statements can be, since nesting them allows us to branch into as many different possibilities as we like.

We have discussed what happens in Min3() if a is smaller than b. If a is not smaller than b, then we enter the else block on lines 8–11 of Min3() and return the smaller of b and c, as shown below. These lines bring us to the end of Min3().

         if b < c
             return b
         else
             return c

Part of the reason why we have separately discussed the if block and the else block in Min3() is that they are both performing the same task, finding the minimum of two numbers. But we have already completed this task when we wrote Min2()! How can we use what we have already done to simplify Min3()?

A fundamental programming paradigm is the ability to use functions as building blocks to construct more complicated functions. Our ongoing example illustrates this concept well. We know that Min3() needs to know the minimum of two numbers in the two highlighted blocks above. We can instead greatly shorten Min3() by using the value returned by the function Min2(). In general, a function that occurs within the body of another function is known as a subroutine, and in this case we say that Min3() calls Min2() as a subroutine.

Min3(a, b, c)
    if a < b
        return Min2(a,c)
    else
        return Min2(b,c)

We should take a moment to explain how the control flow works when one function calls another as a subroutine. Say that we enter the if block in Min3() and reach the following line:

        return Min2(a,c)

Although a function would normally immediately stop at a return statement, Min3() must wait when it encounters the call to Min2(). In the meantime, the control flow passes to Min2(), with input variables of a and c. If a is smaller, then this subroutine returns the value of a; otherwise, it returns the value of c. Only when this subroutine returns the value are we able to use this value and continue on in Min3(). In this case, this value is used in the return statement and Min3() terminates.

One answer to the preceding question is to branch again based on whether a is smaller than b, and then to call Min3(), as shown below.

Min4(a, b, c, d)
    if a < b
        return Min3(a, c, d)
    else
        return Min3(b, c, d)

However, this function can be written even more concisely if we compare the minimum of a and b against the minimum of c and d, and then take the smaller of the two values. This idea can be implemented by the following function that contains only one line!

Min4(a, b, c, d)
     return Min2(Min2(a, b), Min2(c, d))

The Doomsday algorithm, and else if

Before continuing, we will introduce an important variant of the if statement by returning to the party trick that we mentioned in the beginning of the chapter, in which one can quickly determine the day of the week corresponding to a given date in the year. When students are asked how they think this algorithm might work, one of their most common ideas is to memorize the first day of the year, and then count how many days have elapsed between this first day and a given birthday. The problem with this approach is that although it would not take long to determine the day of the week for a date in January or February, dates later in the year would become intensive to calculate.

Instead, we could memorize the day of the week for the first day of every month, and then use this information to count forward in a given month. For example, if April 1st falls on a Sunday, then we would automatically know that April 8th, 15th, 22nd, and 29th also fall on Sundays, so that it would be easy to compute that April 24th falls on a Tuesday by counting two days ahead from the 22nd.

This approach is reasonable but still requires us to memorize quite a lot. The clever trick is instead to memorize a date in every month such that all these days always fall on the same day of the week. The following dates are called doomsdays. Speaking of doomsdays, in 2020, these dates all fell on a Saturday (in 2019, they fell on a Thursday, and in 2018, they fell on a Wednesday).

• January 3rd (or January 4th in leap years)
• February 28th (or February 29th in leap years)
• March 0th (we pretend that this day exists)
• April 4th
• May 9th
• June 6th
• July 11th
• August 8th
• September 5th
• October 10th
• November 7th
• December 12th

These dates are chosen for doomsdays because they can be remembered with ease. February 28th and March 0th correspond to the same day. The doomsdays of the five other even-numbered months (April, June, etc.) have the same number corresponding to the day and month (4/4, 6/6, 8/8, 10/10, 12/12). Four other dates can be remembered via the mnemonic device “I work 9-to-5 at 7–11” (yielding 5/9, 9/5, 7/11, and 11/7). As a result, we only need to memorize four pieces of information: the January and February dates, the even-month rule, and the mnemonic.

The corresponding algorithm for finding the day of the week for a given day and month is called the Doomsday algorithm. An abbreviated function implementing this algorithm in 2020 is shown below.

Doomsday2020(day, month)
     if month = 1
         if day = 4, 11, 18, or 25
             return "Saturday"
         else
             if day = 5, 12, 19, or 26
                 return "Sunday"
             else
                 (and so on...)
     else
         if month = 2
             if day = 7, 14, 21, or 28
                 return "Saturday"
             else
                 if day = 1, 8, 15, or 22
                     return "Sunday"
                 else
                     (and so on...)
         else
             if month = 3
                 (and so on...)

This function is undeniably ugly. The test for whether the month variable is equal to 2 is buried within the first else statement, and the test for whether month is equal to 3 is buried one level lower. In practice, we don’t need the else statements, because if month is not equal to 1, then we can automatically proceed past the if block and test if month is equal to 2. This reasoning leads us to the following streamlined version of Doomsday2020().

Doomsday2020(day, month)
     if month = 1
         if day = 4, 11, 18, or 25
             return "Saturday"
         if day = 5, 12, 19, or 26
             return "Sunday"
         (and so on...)
     if month = 2
         if day = 7, 14, 21, or 28
             return "Saturday"
         if day = 1, 8, 15, or 22
             return "Sunday"
         (and so on...)
     if month = 3
         (and so on...)

In practice, however, if we have 12 different possibilities to check, then we will typically indent them all at the same level and use the keywords else if for all 11 possibilities after the first. This makes our (pseudo)code much more readable, with the control flow jumping directly to the block corresponding to the value of month, and then within that block jumping straight to the block corresponding to the value of day. A final function incorporating else if is shown below.

Doomsday2020(day, month)
     if month = 1
         if day = 4, 11, 18, or 25
             return "Saturday"
         else if day = 5, 12, 19, or 26
             return "Sunday"
         (and so on...)
     else if month = 2
         if day = 7, 14, 21, or 28
             return "Saturday"
         else if day = 1, 8, 15, or 22
             return "Sunday"
         (and so on...)
     else if month = 3
         (and so on...)