NIST

primitive recursive

(definition)

Definition: A total function that 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 recursive functions always terminate. More powerful languages have some functions that 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


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 24 February 2016.
HTML page formatted Fri Feb 23 10:06:08 2018.

Cite this as:
Paul E. Black, "primitive recursive", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 February 2016. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/primitiveRecursive.html