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: Prove a formula is part of the Gentzen System by LadyAnne
Mar 30
new question: A problem about Euler's totient function by mbhatia
new problem: Problem: Show that phi(a^n1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia
new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz
Mar 26
new correction: Misspelled name by DavidSteinsaltz
Mar 21
new correction: underlinetypo by Filipe
Mar 19
new correction: cocycle pro cocyle by pahio
Mar 7
new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier
new image: expected waiting time by robert_dodier
new image: plot W(t) = P(waiting time <= t) by robert_dodier
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.