Bounded
iteration is iteration where the number of times has a determined maximum when it is started.
This is typically (but not necessarily) the case in a
for loop; unbounded iteration is usually expressed in a
while loop.
Bounded iteration has limited expressive power. How limited its power depends on what is meant by it exactly.
-
An algorithm in which all iterations are bounded by fixed constants has constant running time. You could eliminate every iteration by expanding them.
-
An algorithm in which all iterations are bounded by a measure of the input size or by other iterations' fixed loop variables is polynomial. Such a program can be rewritten to use only FOR loops that are bounded to each other's loop variables or to the number of times an special initial loop, that reads all the input, has executed.
-
An algorithm in which all iterations are bounded to expressions evaluated once, at the time the loop is entered, is primitive recursive. (Here the understanding is that the expressions do not implicitly use functions that rely on more powerful forms of iteration - for example, invoking the Ackermann function is not allowed.) This is the most general case; and the term bounded iteration is mostly used to refer to this type of construct.
Imperative programming languages typically offer two kinds of loop constructs:
- a for loop to conveniently express bounded iteration and
- a while loop to express the general case of unbounded iteration.