info prev up next book cdrom email home

Primitive Recursive Function

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).

See also Ackermann Function, Computable Function, Total Function


References

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




© 1996-9 Eric W. Weisstein
1999-05-26