You are here
Homerecursive function
Primary tabs
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^{n}_{m}\colon\mathbb{Z}_{+}^{n}\to\mathbb{Z}_{+}$ with $1\leq m\leq n$ defined as $I^{n}_{m}(x_{1},\ldots,x_{n})=x_{m}$ are recursive functions.
4. (Closure under composition) If $f\colon\mathbb{Z}_{+}^{n}\to\mathbb{Z}_{+}$ is a recursive function and $g_{i}\colon\mathbb{Z}_{+}^{m}\to\mathbb{Z}_{+}$ with $i=1,\ldots n$ are recursive functions, then $h\colon\mathbb{Z}_{+}^{n}\to\mathbb{Z}_{+}$, defined by $h(x_{1},\ldots,x_{n})=f(g_{1}(x_{1},\ldots,x_{m}),\ldots,g_{n}(x_{1},\ldots,x_% {m}))$ is a recursive function.
5. (Closure under primitive recursion) If $f\colon\mathbb{Z}_{+}^{n}\to\mathbb{Z}_{+}$ and $g\colon\mathbb{Z}_{+}^{{n+2}}\to\mathbb{Z}_{+}$ are recursive function, then $h\colon\mathbb{Z}_{+}^{{n+1}}\to\mathbb{Z}_{+}$, defined by the recursion
$h(n+1,x_{1},\ldots,x_{{k}})=g(h(n,x_{1},\ldots,x_{k}),n,x_{1},\ldots,x_{k})$ with the initial condition
$h(0,x_{1},\ldots,x_{k})=f(x_{1},\ldots,x_{k})$ is a recursive function.
6. (Closure under minimization) If $f\colon\mathbb{Z}_{+}^{{n+1}}\to\mathbb{Z}_{+}$ is a recursive function then $g\colon\mathbb{Z}_{+}^{n}\to\mathbb{Z}_{+}$ is a recursive function, where

$g(x_{1},\ldots,x_{n})$ is defined to be $y$, if there exists a $y\in\mathbb{Z}_{+}$ such that
i. $f(0,x_{1},\ldots,x_{n}),f(1,x_{1},\ldots,x_{n}),\ldots,f(y,x_{1},\ldots,x_{n})$ are all defined,
ii. $f(z,x_{1},\ldots,x_{n})\neq 0$ when $1\leq z<y$, and
iii. $f(y,x_{1},\ldots,x_{n})=0$.

$g(x_{1},\ldots,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\colon\mathbb{Z}_{+}^{{n+1}}\to\mathbb{Z}_{+}$, the partial function $g\colon\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{PR}$ 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” for several such characterizations.
Mathematics Subject Classification
03D20 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
Recent Activity
new question: Prime numbers out of sequence by Rubens373
Oct 7
new question: Lorenz system by David Bankom
Oct 19
new correction: examples and OEIS sequences by fizzie
Oct 13
new correction: Define Galois correspondence by porton
Oct 7
new correction: Closure properties on languages: DCFL not closed under reversal by babou
new correction: DCFLs are not closed under reversal by petey
Oct 2
new correction: Many corrections by Smarandache
Sep 28
new question: how to contest an entry? by zorba
new question: simple question by parag
Comments
Arabic maths
Hi all who know the Arabic mathematics! I am curious to know, how in Arabic mathematical texts the mathematical expressions and formulae are written (among other text which goes from right to left)? Are they written from left to right as in European and Chinese languages?
Jussi
Re: Arabic maths
Although the text is written from right to left the numerals are always written from left to right with the highest digit power to the left. The arabic texts might use the arabic numerals (1234567890) or might use the hindu numerals.
Re: Arabic maths
And mathematical formulas among the text?
Re: Arabic maths
Text is always right to left but formulas are always
left to right  same as Western usage.