For-loops (which have a fixed iteration limit) are a special case of while-loops. A function which can be implemented using only for-loops is called primitive recursive. (In contrast, a Computable Function can be coded using a combination of for- and while-loops, or while-loops only.)

The Ackermann Function is the simplest example of a well-defined Total Function which is Computable but not primitive recursive, providing a counterexample to the belief in the early 1900s that every Computable Function was also primitive recursive (Dötzel 1991).

**References**

Dötzel, G. ``A Function to End All Functions.'' *Algorithm: Recreational Programming* **2**, 16-17, 1991.

© 1996-9

1999-05-26