The

**primitive recursive** functions (from the

nonnegative integers to themselves) are the functions of the following class C:

- C contains all projections
`P_i(x_1,...,x_n)=x_i`
- C contains the constant (function)
`z=z()=0`
- C contains the increment function
`I(x)=x+1`
- if C contains the n-ary function
`f(y_1,...,y_n)` and the k-ary functions `g_1(x_1,...,x_k),...,g_n(x_1,...,x_k)`, then C also contains the composition function `h(x_1,...,x_k) = f(g_1(x_1,...,x_k), ..., g_n(x_1,...,x_k))`.
- (
*primitive recursion*) if C contains the functions `c(x_1,...,x_n)`, `g_1(x_1,...,x_n),...,g_n(x_1,...,x_n)` then C also contains the iterated function
h(0,x_1,...,x_n) = c(x_1,...,x_n)
h(m+1,x_1,...,x_n) = h(m, g_1(x_1,...,x_n), ..., g_n(x_1,...,x_n))

- C contains just these functions.

Implementation-wise, the above rules would of course be terribly

inefficient; here we're just concerned with defining the class.

Less formally, C contains the exactly those functions a BASIC program can compute, if we constrain all GOTOs to be forwards, and allow just FOR loops.

Addition, multiplication, exponentiation, integer logarithm, and most other "simple" functions are primitive recursive. Ackermann's function is *not*.

Note that primitive recursive functions are defined for all arguments. Since we know Turing machines (and real computer programs) can enter infinite loops, it should be clear that primitive recursive functions are less powerful than computable functions.