Despite notational differences, contemporary computer languages provide many of the same programming structures. These include basic control structures and data structures. The former provide the means to express algorithms, and the latter provide ways to organize information.
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:
· Sequence—combine the liquid ingredients, and next add the dry ones.
· Conditional—if the tomatoes are fresh then simmer them, but if canned, skip this step.
· 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.