As first shown by Meyer and Ritchie (1967), do-loops (which have a fixed iteration limit) are a special case of while-loops. A function that can be implemented using
only do-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.) Examples of primitive recursive functions include power,
greatest common divisor, and (the function giving the th prime).
Dötzel, G. "A Function to End All Functions." Algorithm: Recreational Programming2, 16-17, 1991.Meyer,
A. and Ritchie, D. "The Complexity of Loop Programs." Proc. 22nd National
ACM Conference. Washington, DC: pp. 465-470, 1967.Péter,
R. Rekursive
Funktionen in der Komputer-Theorie. Budapest: Akad. Kiado, 1951.Wolfram,
S. A
New Kind of Science. Champaign, IL: Wolfram Media, 907,
2002.