In mathematical logic and computer science, the general recursive functions (often shortened to recursive functions) or μrecursive functions are a class of partial functions from natural numbers to natural numbers that are "computable" in an intuitive sense. In computability theory, it is shown that the μrecursive functions are precisely the functions that can be computed by Turing machines(this is one of the theorems that supports the Church–Turing thesis). The μrecursive functions are closely related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every μrecursive function is a primitive recursive function—the most famous example is the Ackermann function. Other equivalent classes of functions are the λrecursive functions and the functions that can be computed by Markov algorithms. The subset of all total recursive functions with values in {0,1} is known in computational complexity theory as the complexity class R.
1. Definition
The μrecursive functions (or general recursive functions) are partial functions that take finite tuples of natural numbers and return a single natural number. They are the smallest class of partial functions that includes the initial functions and is closed under composition, primitive recursion, and the μ operator.
The smallest class of functions including the initial functions and closed under composition and primitive recursion (i.e. without minimisation) is the class of primitive recursive functions. While all primitive recursive functions are total, this is not true of partial recursive functions; for example, the minimisation of the successor function is undefined. The primitive recursive functions are a subset of the total recursive functions, which are a subset of the partial recursive functions. For example, the Ackermann function can be proven to be total recursive, and to be nonprimitive.
Primitive or "basic" functions:
 Constant functions C_{n}^{k}: For each natural number [math]\displaystyle{ n\, }[/math] and every [math]\displaystyle{ k\, }[/math]
[math]\displaystyle{ C_n^k(x_1,\ldots,x_k) \stackrel{\mathrm{def}}{=} n }[/math]
Alternative definitions use instead a zero function as a primitive function that always returns zero, and built the constant functions from the zero function, the successor function and the composition operator.
 Successor function S:
[math]\displaystyle{ S(x) \stackrel{\mathrm{def}}{=} x + 1\, }[/math]
 Projection function [math]\displaystyle{ P_i^k }[/math] (also called the Identity function: For all natural numbers [math]\displaystyle{ i, k }[/math] such that [math]\displaystyle{ 1\le i\le k }[/math]:
[math]\displaystyle{ P_i^k(x_1,\ldots,x_k) \stackrel{\mathrm{def}}{=} x_i \, . }[/math]
Operators (the domain of a function defined by an operator is the set of the values of the arguments such that every function application that must be done during the computation provides a welldefined result):
 Composition operator [math]\displaystyle{ \circ\, }[/math] (also called the substitution operator): Given an mary function [math]\displaystyle{ h(x_1,\ldots,x_m)\, }[/math] and m kary functions [math]\displaystyle{ g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k) }[/math]:
[math]\displaystyle{ h \circ (g_1, \ldots, g_m) \stackrel{\mathrm{def}}{=} f, \quad\text{where}\quad f(x_1,\ldots,x_k) = h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k)). }[/math]
This means that [math]\displaystyle{ f(x_1,\ldots,x_k) }[/math] is defined only if [math]\displaystyle{ g_1(x_1,\ldots,x_k),\ldots, g_m(x_1,\ldots,x_k), }[/math] and [math]\displaystyle{ h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k)) }[/math] are all defined.
 Primitive recursion operator [math]\displaystyle{ \rho\, }[/math]: Given the kary function [math]\displaystyle{ g(x_1,\ldots,x_k)\, }[/math] and k+2 ary function [math]\displaystyle{ h(y,z,x_1,\ldots,x_k)\, }[/math]:
[math]\displaystyle{ \begin{align} \rho(g, h) &\stackrel{\mathrm{def}}{=} f \quad\text{where the k+1 ary function } f \text{ is defined by}\\ f(0,x_1,\ldots,x_k) &= g(x_1,\ldots,x_k) \\ f(S(y),x_1,\ldots,x_k) &= h(y,f(y,x_1,\ldots,x_k),x_1,\ldots,x_k)\,.\end{align} }[/math]
This means that [math]\displaystyle{ f(y,x_1,\ldots,x_k) }[/math] is defined only if [math]\displaystyle{ g(x_1,\ldots,x_k) }[/math] and [math]\displaystyle{ h(z,f(z,x_1,\ldots,x_k),x_1,\ldots,x_k) }[/math] are defined for all [math]\displaystyle{ z\lt y. }[/math]
 Minimization operator [math]\displaystyle{ \mu\, }[/math]: Given a (k+1)ary function [math]\displaystyle{ f(y, x_1, \ldots, x_k)\, }[/math], the kary function [math]\displaystyle{ \mu(f) }[/math] is defined by:
[math]\displaystyle{ \begin{align} \mu(f)(x_1, \ldots, x_k) = z \stackrel{\mathrm{def}}{\iff}\ f(i, x_1, \ldots, x_k)&\gt 0 \quad \text{for}\quad i=0, \ldots, z1 \quad\text{and}\\ f(z, x_1, \ldots, x_k)&=0\quad \end{align} }[/math]
Intuitively, minimisation seeks—beginning the search from 0 and proceeding upwards—the smallest argument that causes the function to return zero; if there is no such argument, of if one encounters an argument for which f is not defined, then the search never terminates, and [math]\displaystyle{ \mu(f) }[/math] is not defined for the argument [math]\displaystyle{ (x_1, \ldots, x_k). }[/math]
(Note: While some textbooks use the μoperator as defined here,^{[1]}^{[2]} others like ^{[3]}^{[4]} demand that the μoperator is applied to total functions [math]\displaystyle{ f }[/math] only. Although this restricts the μoperator as compared to the definition given here, the class of μrecursive functions remains the same, which follows from Kleene's Normalform Theorem.^{[1]}^{[2]} The only difference is, that it becomes undecidable whether some text satisfies the requirements given for the base functions and operators as it is not semidecidable (hence undecidable) whether a computable (i.e. μrecursive) function is total.^{[3]})
The strong equality operator [math]\displaystyle{ \simeq }[/math] can be used to compare partial μrecursive functions. This is defined for all partial functions f and g so that
 [math]\displaystyle{ f(x_1,\ldots,x_k) \simeq g(x_1,\ldots,x_l) }[/math]
holds if and only if for any choice of arguments either both functions are defined and their values are equal or both functions are undefined.
2. Equivalence with Other Models of Computability
In the equivalence of models of computability, a parallel is drawn between Turing machines that do not terminate for certain inputs and an undefined result for that input in the corresponding partial recursive function. The unbounded search operator is not definable by the rules of primitive recursion as those do not provide a mechanism for "infinite loops" (undefined values).
3. Normal Form Theorem
A normal form theorem due to Kleene says that for each k there are primitive recursive functions [math]\displaystyle{ U(y)\! }[/math] and [math]\displaystyle{ T(y,e,x_1,\ldots,x_k)\! }[/math] such that for any μrecursive function [math]\displaystyle{ f(x_1,\ldots,x_k)\! }[/math] with k free variables there is an e such that
 [math]\displaystyle{ f(x_1,\ldots,x_k) \simeq U(\mu y\, T(y,e,x_1,\ldots,x_k)) }[/math].
The number e is called an index or Gödel number for the function f.^{[5]}^{:52–53} A consequence of this result is that any μrecursive function can be defined using a single instance of the μ operator applied to a (total) primitive recursive function.
Minsky (1967) observes (as does BoolosBurgessJeffrey (2002) pp. 94–95) that the U defined above is in essence the μrecursive equivalent of the universal Turing machine:
 To construct U is to write down the definition of a generalrecursive function U(n, x) that correctly interprets the number n and computes the appropriate function of x. to construct U directly would involve essentially the same amount of effort, and essentially the same ideas, as we have invested in constructing the universal Turing machine. (italics in original, Minsky (1967) p. 189)
4. Symbolism
A number of different symbolisms are used in the literature. An advantage to using the symbolism is a derivation of a function by "nesting" of the operators one inside the other is easier to write in a compact form. In the following we will abbreviate the string of parameters x_{1}, ..., x_{n} as x:
 Constant function: Kleene uses " Cnq(x) = q " and BoolosBurgessJeffrey (2002) (BBJ) use the abbreviation " const_{n}( x) = n ":

 e.g. C713 ( r, s, t, u, v, w, x ) = 13
 e.g. const_{13} ( r, s, t, u, v, w, x ) = 13
 Successor function: Kleene uses x' and S for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows:

 S(a) = a +1 =_{def} a', where 1 =_{def} 0', 2 =_{def} 0 ' ', etc.
 Identity function: Kleene (1952) uses " Uni " to indicate the identity function over the variables x_{i}; BBJ use the identity function idni over the variables x_{1} to x_{n}:
 Uni( x ) = idni( x ) = x_{i}
 e.g. U73 = id73 ( r, s, t, u, v, w, x ) = t
 Composition (Substitution) operator: Kleene uses a boldface Smn (not to be confused with his S for "successor" ! ). The superscript "m" refers to the m^{th} of function "f_{m}", whereas the subscript "n" refers to the n^{th} variable "x_{n}":
 If we are given h( x )= g( f_{1}(x), ... , f_{m}(x) )
 h(x) = Snm(g, f_{1}, ... , f_{m} )
 In a similar manner, but without the sub and superscripts, BBJ write:
 h(x')= Cn[g, f_{1} ,..., f_{m}](x)
 Primitive Recursion: Kleene uses the symbol " R^{n}(base step, induction step) " where n indicates the number of variables, BBJ use " Pr(base step, induction step)(x)". Given:

 base step: h( 0, x )= f( x ), and
 induction step: h( y+1, x ) = g( y, h(y, x),x )
 Example: primitive recursion definition of a + b:

 base step: f( 0, a ) = a = U11(a)
 induction step: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U32( b, c, a ))
 R^{2} { U11(a), S [ (U32( b, c, a ) ] }
 Pr{ U11(a), S[ (U32( b, c, a ) ] }
Example: Kleene gives an example of how to perform the recursive derivation of f(b, a) = b + a (notice reversal of variables a and b). He starts with 3 initial functions

 S(a) = a'
 U11(a) = a
 U32( b, c, a ) = c
 g(b, c, a) = S(U32( b, c, a )) = c'
 base step: h( 0, a ) = U11(a)
 induction step: h( b', a ) = g( b, h( b, a ), a )
He arrives at:

 a+b = R^{2}[ U11, S31(S, U32) ]
5. Examples
 Fibonacci number
 McCarthy 91 function