recursive function
Intuitively, a recursive function^{} is a positive integer valued function of one or more positive integer arguments which may be computed by a definite algorithm^{}.
Recursive functions may be defined more rigorously as the smallest class of partial functions^{} from ${\mathbb{Z}}_{+}^{n}\to {\mathbb{Z}}_{+}$ satisfying the following six criteria:

1.
The constant function $c:{\mathbb{Z}}_{+}\to {\mathbb{Z}}_{+}$ defined by $c(x)=1$ for all $x\in {\mathbb{Z}}_{+}$ is a recursive function.

2.
The addition^{} function $+:{\mathbb{Z}}_{+}^{2}\to {\mathbb{Z}}_{+}$ and the multiplication function $\times :{\mathbb{Z}}_{+}^{2}\to {\mathbb{Z}}_{+}$ are recursive function.

3.
The projection functions ${I}_{m}^{n}:{\mathbb{Z}}_{+}^{n}\to {\mathbb{Z}}_{+}$ with $1\le m\le n$ defined as ${I}_{m}^{n}({x}_{1},\mathrm{\dots},{x}_{n})={x}_{m}$ are recursive functions.

4.
(Closure under composition^{}) If $f:{\mathbb{Z}}_{+}^{n}\to {\mathbb{Z}}_{+}$ is a recursive function and ${g}_{i}:{\mathbb{Z}}_{+}^{m}\to {\mathbb{Z}}_{+}$ with $i=1,\mathrm{\dots}n$ are recursive functions, then $h:{\mathbb{Z}}_{+}^{n}\to {\mathbb{Z}}_{+}$, defined by $h({x}_{1},\mathrm{\dots},{x}_{n})=f({g}_{1}({x}_{1},\mathrm{\dots},{x}_{m}),\mathrm{\dots},{g}_{n}({x}_{1},\mathrm{\dots},{x}_{m}))$ is a recursive function.

5.
(Closure under primitive recursion) If $f:{\mathbb{Z}}_{+}^{n}\to {\mathbb{Z}}_{+}$ and $g:{\mathbb{Z}}_{+}^{n+2}\to {\mathbb{Z}}_{+}$ are recursive function, then $h:{\mathbb{Z}}_{+}^{n+1}\to {\mathbb{Z}}_{+}$, defined by the recursion
$$h(n+1,{x}_{1},\mathrm{\dots},{x}_{k})=g(h(n,{x}_{1},\mathrm{\dots},{x}_{k}),n,{x}_{1},\mathrm{\dots},{x}_{k})$$ with the initial condition
$$h(0,{x}_{1},\mathrm{\dots},{x}_{k})=f({x}_{1},\mathrm{\dots},{x}_{k})$$ is a recursive function.

6.
(Closure under minimization) If $f:{\mathbb{Z}}_{+}^{n+1}\to {\mathbb{Z}}_{+}$ is a recursive function then $g:{\mathbb{Z}}_{+}^{n}\to {\mathbb{Z}}_{+}$ is a recursive function, where

–
$g({x}_{1},\mathrm{\dots},{x}_{n})$ is defined to be $y$, if there exists a $y\in {\mathbb{Z}}_{+}$ such that

i.
$f(0,{x}_{1},\mathrm{\dots},{x}_{n}),f(1,{x}_{1},\mathrm{\dots},{x}_{n}),\mathrm{\dots},f(y,{x}_{1},\mathrm{\dots},{x}_{n})$ are all defined,

ii.
$f(z,{x}_{1},\mathrm{\dots},{x}_{n})\ne 0$ when $$, and

iii.
$f(y,{x}_{1},\mathrm{\dots},{x}_{n})=0$.

i.

–
$g({x}_{1},\mathrm{\dots},{x}_{n})$ is undefined otherwise.

–
The operation^{} whereby $h$ was constructed from $f$ and $g$ in criterion 5 is known as primitive recursion. The operation described in criterion 6 is known as minimization. That is to say, for any given function $f:{\mathbb{Z}}_{+}^{n+1}\to {\mathbb{Z}}_{+}$, the partial function $g:{\mathbb{Z}}_{+}^{n}\to {\mathbb{Z}}_{+}$ constructed as in criterion 6 is known as the minimization of $f$ and is denoted by $g=\mu f$.
The smallest set of functions satisfying criteria 15, but not criterion 6, is known as the set of primitive recursive functions^{}. Therefore, the set $\mathcal{R}$ of all recursive function is the closure of the set $\mathcal{P}\mathcal{R}$ of primitive recursive function with respect to minimization. It can be shown that $\mathcal{R}$ is exactly the set of Turingcomputable functions. In terms of programming languages, a function is recursive iff it can be computed by a program involving the DO WHILE loops (minimization).
With some work, it can be shown that the class of recursive functions can be characterized by considerably weaker sets of criteria than those given above. See the entry “alternative characterizations of recursive functions (http://planetmath.org/AlternativeCharacterizationsOfRecursiveFunctions)” for several such characterizations^{}.
Title  recursive function 
Canonical name  RecursiveFunction 
Date of creation  20130322 14:34:35 
Last modified on  20130322 14:34:35 
Owner  rspuzio (6075) 
Last modified by  rspuzio (6075) 
Numerical id  27 
Author  rspuzio (6075) 
Entry type  Definition 
Classification  msc 03D20 
Synonym  unbounded minimization 
Related topic  PrimitiveRecursive 
Related topic  RecursiveFunctionIsURMComputable 
Related topic  BoundedMinimization 
Defines  primitive recursion 
Defines  minimization 