primitive recursive function
To define what a primitive recursive function^{} is, the following notations are used:
$\mathcal{F}=\bigcup \{{F}_{k}\mid k\in \mathbb{N}\}$, where for each $k\in \mathbb{N}\text{,}{F}_{k}=\{f\mid f:{\mathbb{N}}^{k}\to \mathbb{N}\}$.
Definition. The set of primitive recursive functions is the smallest subset $\mathcal{P}\mathcal{R}$ of $\mathcal{F}$ where:

1.
(zero function) $z\in \mathcal{P}\mathcal{R}\cap {F}_{1}$, given by $z(n):=0$;

2.
(successor function) $s\in \mathcal{P}\mathcal{R}\cap {F}_{1}$, given by $s(n):=n+1$;

3.
(projection functions) ${p}_{m}^{k}\in \mathcal{P}\mathcal{R}\cap {F}_{k}$, where $m\le k$, given by ${p}_{m}^{k}({n}_{1},\mathrm{\dots},{n}_{k}):={n}_{m}$;

4.
$\mathcal{P}\mathcal{R}$ is closed under composition: If $\{{g}_{1},\mathrm{\dots},{g}_{m}\}\subseteq \mathcal{P}\mathcal{R}\cap {F}_{k}$ and $h\in \mathcal{P}\mathcal{R}\cap {F}_{m}$, then $f\in \mathcal{P}\mathcal{R}\cap {F}_{k}$, where
$$f({n}_{1},\mathrm{\dots},{n}_{k})=h({g}_{1}({n}_{1},\mathrm{\dots},{n}_{k}),\mathrm{\dots},{g}_{m}({n}_{1},\mathrm{\dots},{n}_{k}));$$ 
5.
$\mathcal{P}\mathcal{R}$ is closed under primitive recursion: If $g\in \mathcal{P}\mathcal{R}\cap {F}_{k}$ and $h\in \mathcal{P}\mathcal{R}\cap {F}_{k+2}$, then $f\in \mathcal{P}\mathcal{R}\cap {F}_{k+1}$, where
$f({n}_{1},\mathrm{\dots},{n}_{k},0)$ $=$ $g({n}_{1},\mathrm{\dots},{n}_{k})$ $f({n}_{1},\mathrm{\dots},{n}_{k},s(n))$ $=$ $h({n}_{1},\mathrm{\dots},{n}_{k},n,f({n}_{1},\mathrm{\dots},{n}_{k},n)).$
Many of the arithmetic functions that we encounter in basic math are primitive recursive, including addition^{}, multiplication, and exponentiation. More examples can be found in this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions).
Primitive recursive functions are computable by Turing machines^{}. In fact, it can be shown that $\mathcal{P}\mathcal{R}$ is precisely the set of functions computable by programs using FOR NEXT loops. However, not all Turingcomputable functions are primitive recursive: the Ackermann function^{} is one such example.
Since $\mathcal{F}$ is countable^{}, so is $\mathcal{P}\mathcal{R}$. Moreover, $\mathcal{P}\mathcal{R}$ is recursively enumerable^{} (can be listed by a Turing machine).
Remarks.

[1]
Every primitive recursive function is total, since it is built from $z$, $s$, and ${p}_{m}^{k}$, each of which is total, and that functional^{} composition, and primitive recursion preserve totalness. By including $\mathrm{\varnothing}$ in $\mathcal{P}\mathcal{R}$ above, and close it by functional composition and primitive recursion, one gets the set of partial primitive recursive functions.

[2]
Primitive recursiveness can be defined on subsets of ${\mathbb{N}}^{k}$: a subset $S\subseteq {\mathbb{N}}^{k}$ is primitive recursive if its characteristic function^{} ${\phi}_{S}$, which is defined as
$${\phi}_{S}(x):=\{\begin{array}{cc}1\hfill & \text{if}x\in S,\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$ is primitive recursive.

[3]
Likewise, primitive recursiveness can be defined for predicates^{} over tuples of natural numbers^{}. A predicate $\mathrm{\Phi}(\bm{x})$, where $\bm{x}\in {\mathbb{N}}^{k}$, is said to be primitive recursive if the set $S(\mathrm{\Phi}):=\{\bm{x}\mid \mathrm{\Phi}(\bm{x})\}$ is primitive recursive.
Title  primitive recursive function 

Canonical name  PrimitiveRecursiveFunction 
Date of creation  20130322 12:33:19 
Last modified on  20130322 12:33:19 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  19 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D20 
Synonym  primitive recursive 
Related topic  RecursiveFunction 
Defines  primitive recursive set 
Defines  primitive recursive predicate 
Defines  partial primitive recursive function 