(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 Black.
Entry modified 17 December 2004.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "primitive recursive", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/primitivrecr.html