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.