From Encyclopedia of Mathematics
Jump to: navigation, search

A sequence of actions performed according to a law and having a precise description — an algorithm.

A procedure is a special way of formulating a program for partially solving a problem that is part of another larger problem; it is a fundamental construction in algorithmic languages (cf. Algorithmic language).

A procedure is a principal tool for overcoming complexities in programming by way of systematic partitioning of a problem in parts. One distinguishes two kinds of methods for specifying procedures in programming: descending and ascending. In the descending approach a procedure arises in a one-level partitioning of the problem into a small number of connected subproblems; thus, a procedure is identified with the structure of its program. In the ascending approach a procedure is preserved so that it can be used as an elementary action in the future for solving wider problems.

The program formed by a procedure usually contains free variables, called the formal parameters of the procedure. When calling upon a procedure the formal parameters take their values, called factual parameters. The description of a procedure usually consists of four parts: the body of the procedure, i.e. the proper program formed by it; the name of the procedure; the list of formal parameters; and the attributes, the list of properties of the procedure. Usually the attributes characterize the set to which the values of the formal parameters and result of the procedure belong. The simplest kind of procedure is a function procedure. For it the formal parameters are arguments of the function, while a call upon a function procedure, having the form of the name of the procedure followed by a list of the factual parameters between brackets, denotes the "command" of computing the value of the function corresponding to these parameters.


Some authors make a specific distinction between algorithms and procedures. Algorithms are prescriptions of sequences of actions which should always terminate after a finite number of steps. For procedures the termination is not required; a procedure may perform a non-terminating computation producing meaningfull output results during the course of its computations. This distinction makes it possible to describe computational processes which accept their input by termination rather than by accepting state.


[a1] J.E. Hopcroft, J.D. Ulman, "Introduction to automata theory, languages and computation" , Addison-Wesley (1979)
How to Cite This Entry:
Procedure. A.P. Ershov (originator), Encyclopedia of Mathematics. URL:
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098