Content deleted Content added
Mearrcteell (talk | contribs) If we don't exclude functions recursively calling themselves, the restriction to for-loops is useless in delimiting the PR functions. Tags: Reverted Visual edit |
Mearrcteell (talk | contribs) Nevermind, this is clarified by the section "Computer language definition". |
||
Line 1:
{{Short description|Function computable with bounded loops}}
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)
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.<ref>Brainerd and Landweber, 1974</ref> 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.<ref>Hartmanis, 1989</ref> 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.
| |||