
recursive function

(Definition)


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 largest class of partial functions from
satisfying the following six criteria:
 The constant function
defined by for all
is a recursive function.
 The addition function
and the multiplication function
are recursive function.
 The projection functions
with
defined as
are recursive functions.
 (Closure under composition) If
is a recursive function and
with
are recursive functions, then
, defined by
is a recursive function.
 (Closure under primitive recursion)If
and
are recursive function, then
, defined by the recursion
with the initial condition
is a recursive function.
 (Closure under minimization) If
is a recursive function then
is a recursive function, where is defined to equal if there exists a
such that

are all defined,

when
, and

, otherwise
is undefined.
The operation whereby was constructed from and 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
, the partial function
constructed as in criterion 6 is known as the minimization of and is denoted by .
The smallest set of functions satisfying criteria 15, but not criterion 6, is known as the set of primitive recursive functions.
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.

"recursive function" is owned by rspuzio. [ full author list (3) ]


(view preamble)
Also defines: 
primitive recursive function, primitive recursion 
Crossreferences: characterizations, weaker, operation, initial condition, composition, closure, projection, constant function, partial functions, class, arguments, function, integer, positive
There are 11 references to this entry.
This is version 18 of recursive function, born on 20040904, modified 20061109.
Object id is 6135, canonical name is RecursiveFunction.
Accessed 6028 times total.
Classification:
AMS MSC:  03D20 (Mathematical logic and foundations :: Computability and recursion theory :: Recursive functions and relations, subrecursive hierarchies) 



Pending Errata and Addenda







