Primitive recursion

In computability theory, primitive recursive functions are a class of functions that are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions (µ-recursive functions are also called partial recursive). Primitive recursive functions form an important building block on the way to a full formalization of computability. These functions are also important in proof theory.

Most of the functions normally studied in number theory are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the nth prime are all primitive recursive. So are many approximations to real-valued functions. In fact, it is difficult to devise a total recursive function that is not primitive recursive, although some are known (see the section on Limitations below). The set of primitive recursive functions is known as PR in computational complexity theory.

The primitive recursive functions are among the number-theoretic functions, which are functions from the natural numbers (nonnegative integers) {0, 1, 2, ...} to the natural numbers. These functions take n arguments for some natural number n and are called n-ary.

The basic primitive recursive functions are given by these axioms:

...
Wikipedia