An algorithm can look endlessly varied from the outside, but it is assembled from a very small kit, and this section is organized as a climb from the kit to finished work. At the bottom are three control structures: sequencing, selection, and iteration. Above them are the ways those structures combine and extend, which are tracing them, nesting them, repeating through recursion, and generalizing them into reusable functions. Above those are patterns, recognizable arrangements that programmers reuse for common jobs, such as totaling a list or finding its largest value. The section ends with Euclid's algorithm, a classic that draws on all of it. The typed loop notation that these examples use is introduced under "Variable-focused iteration."

The three control structures#

Sequencing is the most basic and the easiest to overlook: instructions run one after another, in order, so swapping statements can change the result.¹ Subtracting a coupon and then applying a multiplier gives a different price than doing the same steps the other way around. An output placed before the line that assigns a value displays whatever was there before. Sequence also explains why exchanging two values takes three steps. The assignment x = y overwrites x, and if y = x follows, both variables hold the same value, so you have to save the old value in a temporary variable first:

01 int x = 3
02 int y = 8
03 int temp = x
04 x = y
05 y = temp

Running strictly in order would make a program do the same thing every time, and selection adds the ability to choose. Conditions determine which code runs. In an if/elseif/else chain, only the first true branch runs, and the rest are skipped, so the order of the conditions matters.² A grading chain that tests score >= 60 first gives a 95 the same letter as a 60, because that first test succeeds and nothing further is checked. This has a useful side: by the time a program reaches a later elseif, it already knows that the earlier conditions were false, so it needn't test them again. Separate if statements behave differently, because each is evaluated on its own, and several can run. Conditions also have to be real bool expressions. To test for an even number, write if (n % 2 == 0), since a number can't serve directly as a condition.

Iteration adds repetition. A for loop suits a known number of repetitions, and a while loop repeats as long as a condition is true, which suits cases where the count can't be known ahead of time, such as asking until a password is correct.³ In both, the condition says when to continue and doesn't say when to stop, so a loop printing 1 through 5 needs i <= 5, and i == 5 would never start. Indentation defines what is inside the loop. A line that updates the counter but sits outside the indented body never runs during the loop, so the program never stops.

Tracing, nesting, and recursion#

Loops are where programs get hard to follow in your head, and the reliable method is to write it down. To trace a loop, record each variable's value at each iteration in a table, checking the loop's start, its stopping condition, and how the counter changes. The final test that fails doesn't count as a pass through the body: a loop with i starting at 10, falling by 2, and continuing while i > 0 prints five times, for 10, 8, 6, 4, and 2. A wrong result can be found at its first appearance in the table, which is what makes tracing a debugging tool as well as a reading skill.

Tracing becomes especially useful when one loop sits inside another. In a nested loop, the inner loop runs completely for each repetition of the outer loop, so the total number of inner repetitions is often the product of the two counts.

01 int count = 0
02 for (int i = 0; i < 3; i = i + 1)
03   for (int j = 0; j < 4; j = j + 1)
04     count = count + 1
05 output(count)

This outputs >>> 12. If the inner bound depends on the outer variable, as in j <= i, add up the varying counts: with i running from 1 to 3, the inner loop runs 1, 2, and 3 times, for a total of 6. In a two-dimensional array, the outer loop usually moves through rows and the inner through columns, reading each value as grid[r, c]. Nesting also makes it matter where a variable is set. A row total or a yes-or-no flag that applies to each row has to be reset inside the outer loop, or the value from one row carries over into the next. Where a language provides break, it exits only the nearest loop, so breaking out of an inner loop lets the outer loop carry on with its next row.

Loops aren't the only way to repeat. In recursion, a function calls itself on a smaller version of a problem. It needs a base case that stops the calls and a recursive case that moves toward it, and without these, it never finishes.

01 function power(int n)
02   if (n == 0)
03     return 1
04   return 2 * power(n - 1)
05
06 output(power(4))

This outputs >>> 16. To trace it, follow the calls down from power(4) to power(0), which returns 1, and then follow the returns back up, as each pending call multiplies by 2. "Smaller" can take other forms than counting down. A function that checks whether a word reads the same in both directions can compare the two end characters and call itself with both positions moved inward, stopping when they meet. Each pending call stays on the call stack, a structure described in 0002.h, until the calls beneath it return, so recursion can use more memory than a loop for the same result. A recursive sum and a loop that computes the same sum give identical answers, but the recursive one holds on to a pending call for every step.

Reusability#

Functions like these are more useful the less they assume. Reusability means replacing specific repeated code with a general function, so that it can be applied to new inputs. Write area(int w, int h) rather than area5 and area7, and give a letter-counting function a letter parameter rather than writing one function per letter. A tax function that takes the rate as a parameter never has to be copied and edited for a new rate. Parameters are the mechanism: anything that might change becomes an input, and the logic remains in one place, as in 0002.d.

Patterns built from these structures#

Certain combinations of these structures come up so often that experienced programmers recognize them on sight, and learning a few is a large part of learning to read code. The accumulator pattern initializes a variable before a loop and updates it on each pass, for totals, counts, or strings built up with concat.

01 int[] values = [3, 5, 9]
02 int total = 0
03 for (int i = 0; i < values.size[1]; i = i + 1)
04   total = total + values[i]
05 output(total)

This outputs >>> 17. The placement of line 02 is the classic source of error, since initializing inside the loop resets the variable on every pass, leaving only the last value. The update distinguishes the two main uses: counting adds 1, and totaling adds a value. Adding a condition around the update gives you a count of only the scores above a cutoff, or a total of only the dues that were paid. When building a string, remember to store what concat returns, as in list = concat(list, ",", names[i]), because calling it alone changes nothing.

Finding a maximum or minimum is a close relative, with the accumulator replaced by a best-so-far value. Set a variable to the first element, loop through the rest, and replace it whenever a larger value appears.²

01 int[] temps = [-4, -9, -2, -7]
02 int largest = temps[0]
03 for (int i = 1; i < temps.size[1]; i = i + 1)
04   if (temps[i] > largest)
05     largest = temps[i]
06 output(largest)

This outputs >>> -2. Starting at 0 instead would fail here, because when all values are negative, nothing ever beats it. The comparison operator decides ties: a strict > keeps the first of several ties, and >= keeps the last. Reversing the comparison finds a minimum, and a repeated minimum doesn't count as a new one under <. To report where the largest value occurs, store the index, and read the value through it, as in if (scores[i] > scores[best]), which also lets you use that index in a parallel array of names. The comparison can be on any property of the elements, but > isn't defined for String values, so to find the longest word, compare .len.

A classic algorithm: Euclid's#

Euclid's algorithm shows how far these simple parts can go. It finds a greatest common factor by repeatedly replacing a pair of numbers with the smaller number and the remainder of dividing the larger by the smaller, until the remainder is 0.

01 function gcf(int a, int b)
02   while (b != 0)
03     int r = a % b
04     a = b
05     b = r
06   return a

The pair (48, 18) becomes (18, 12), (12, 6), and (6, 0), so the answer is 6. A while loop fits, since the number of steps isn't known in advance. The body is the swap from the start of this section in another form. Without the temporary r, line 04 would destroy a before the remainder is computed, and b % b is always 0. If the smaller number is passed first, the first pass simply exchanges them. The result is a practical tool: dividing the top and bottom of 42/56 by their greatest common factor, 14, reduces the fraction to 3/4.

Every example here has been written as a series of steps that change variables. That is such a familiar way to program that it can seem like the only one, but it is one of several, and the next section compares them.

• sequencing: running instructions one after another, in order
• selection: using conditions to choose which code runs
• iteration: repeating code, with a for loop for a known count or a while loop for as long as a condition is true
• trace: recording each variable's value at each iteration in a table
• nested loop: a loop inside a loop, with the inner one running completely for each outer repetition
• recursion: a function calling itself on a smaller version of a problem
• base case: the condition that stops recursive calls
• recursive case: the call that moves toward the base case
• call stack: the structure that holds pending function calls
• reusability: writing general functions with parameters in place of specific repeated code
• accumulator pattern: initializing a variable before a loop and updating it on each pass
• Euclid's algorithm: finding a greatest common factor by repeatedly replacing a pair with the smaller number and the remainder

Practice: practice questions for 0002.f

1. MWC1, Turtle: first programs, sequence, errors and bugs. ↩

2. MWC1, Scatter: top-down and bottom-up problem solving, conditionals, return values, minimums and maximums, and plots. ↩ ↩2

3. MWC1, Iteration: lists, for loops, and range. ↩