Editing Primitive recursive function (section)

{{Short description|Function computable with bounded loops}}
{{CS1 config|mode=cs2}}
In [[computability theory]], a '''primitive recursive function''' is, roughly speaking, a function that can be computed by a [[computer program]] whose [[loop (programming)|loops]] are all [[For loop|"for" loops]] (that is, an upper bound of the number of iterations of every loop is fixed before entering the loop). Primitive recursive functions form a strict [[subset]] of those [[general recursive function]]s that are also [[total function]]s. 

The importance of primitive recursive functions lies in the fact that most [[computable function]]s that are studied in [[number theory]] (and more generally in mathematics) are primitive recursive. For example, [[addition]] and [[division (mathematics)|division]], the [[factorial]] and [[exponential function]], and the function which returns the ''n''th prime are all primitive recursive.{{sfn|Brainerd|Landweber|1974}} In fact, for showing that a computable function is primitive recursive, it suffices to show that its [[time complexity]] is bounded above by a primitive recursive function of the input size.{{sfn|Hartmanis|1989}} It is hence not particularly easy to devise a [[computable function]] that is ''not'' primitive recursive; some examples are shown in section {{slink||Limitations}} below.

The set of primitive recursive functions is known as [[PR (complexity)|PR]] in [[computational complexity theory]].