Control structures
Programs written in procedural languages, the most common kind, are like recipes, having lists of ingredients and step-by-step instructions for using them. The three basic control structures in virtually every procedural language are:
- 1. Sequence—combine the liquid ingredients, and next add the dry ones.
- 2. Conditional—if the tomatoes are fresh then simmer them, but if canned, skip this step.
- 3. Iterative—beat the egg whites until they form soft peaks.
Sequence is the default control structure; instructions are executed one after another. They might, for example, carry out a series of arithmetic operations, assigning results to variables, to find the roots of a quadratic equation ax2 + bx + c = 0. The conditional IF-THEN or IF-THEN-ELSE control structure allows a program to follow alternative paths of execution. Iteration, or looping, gives computers much of their power. They can repeat a sequence of steps as often as necessary, and appropriate repetitions of quite simple steps can solve complex problems.
These control structures can be combined. A sequence may contain several loops; a loop may contain a loop nested within it, or the two branches of a conditional may each contain sequences with loops and more conditionals. In the “pseudocode” used in this article, “*” indicates multiplication and “←” is used to assign values to variables. The following programming fragment employs the IF-THEN structure for finding one root of the quadratic equation, using the quadratic formula:
.
The quadratic formula assumes that a is nonzero and that the discriminant (the portion within the square root sign) is not negative (in order to obtain a real number root). Conditionals check those assumptions:
- IF a = 0 THEN
- ROOT ← −c/b
- ELSE
- DISCRIMINANT ← b*b − 4*a*c
- IF DISCRIMINANT ≥ 0 THEN
- ROOT ← (−b + SQUARE_ROOT(DISCRIMINANT))/2*a
- ENDIF
- ENDIF
The SQUARE_ROOT function used in the above fragment is an example of a subprogram (also called a procedure, subroutine, or function). A subprogram is like a sauce recipe given once and used as part of many other recipes. Subprograms take inputs (the quantity needed) and produce results (the sauce). Commonly used subprograms are generally in a collection or library provided with a language. Subprograms may call other subprograms in their definitions, as shown by the following routine (where ABS is the absolute-value function). SQUARE_ROOT is implemented by using a WHILE (indefinite) loop that produces a good approximation for the square root of real numbers unless x is very small or very large. A subprogram is written by declaring its name, the type of input data, and the output:
- FUNCTION SQUARE_ROOT(REAL x) RETURNS REAL
- ROOT ← 1.0
- WHILE ABS(ROOT*ROOT − x) ≥ 0.000001
- AND WHILE ROOT ← (x/ROOT + ROOT)/2
- RETURN ROOT
Subprograms can break a problem into smaller, more tractable subproblems. Sometimes a problem may be solved by reducing it to a subproblem that is a smaller version of the original. In that case the routine is known as a recursive subprogram because it solves the problem by repeatedly calling itself. For example, the factorial function in mathematics (n! = n∙(n−1)⋯3∙2∙1—i.e., the product of the first n integers), can be programmed as a recursive routine:
- FUNCTION FACTORIAL(INTEGER n) RETURNS INTEGER
- IF n = 0 THEN RETURN 1
- ELSE RETURN n * FACTORIAL(n−1)
The advantage of recursion is that it is often a simple restatement of a precise definition, one that avoids the bookkeeping details of an iterative solution.
At the machine-language level, loops and conditionals are implemented with branch instructions that say “jump to” a new point in the program. The “goto” statement in higher-level languages expresses the same operation but is rarely used because it makes it difficult for humans to follow the “flow” of a program. Some languages, such as Java and Ada, do not allow it.