(definition)
Definition: A total function which can be written using only nested conditional (if-then-else) statements and fixed iteration (for) loops.
See also computable.
Note: Ackermann's function is computable, but is not primitive recursive. Primitive recursion functions always terminate. More powerful languages have some functions which cannot be proved to either terminate or run forever.
After Algorithms and Theory of Computation Handbook, footnote, page 26-13, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 17 December 2004.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "primitive recursive", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 17 December 2004. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/primitivrecr.html
