Recursive Function
The term "recursive function" is often used informally to describe any function that is defined with recursion. There are several formal counterparts to this informal definition, many of which only differ in trivial respects.
Kleene (1952) defines a "partial recursive function" of nonnegative integers to be any function 
that is defined by a noncontradictory
system of equations whose left and right sides are composed from (1) function symbols
(for example, 
, 
, 
, etc.), (2) variables
for nonnegative integers (for example, 
, 
, 
, etc.), (3) the
constant 0, and (4) the successor function 
.
For example,
 |  |  |
(1)
|
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
defines 
to be the function 
that computes
the product of 
and 
.
Note that the equations might not uniquely determine the value of 
for every possible
input, and in that sense the definition is "partial." If the system of
equations determines the value of f for every input, then the definition is said
to be "total." When the term "recursive function" is used alone,
it is usually implicit that "total recursive function" is intended. Note
that some authors use the term "general
recursive function to mean partial recursive function, although others use it
to mean "total recursive function."
The set of functions that can be defined recursively in this manner is known to be equivalent to the set of functions computed by Turing machines and by the lambda calculus.
Contact the MathWorld Team
Ackermann(3,3)
