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.
Wolfram (2023) discusses the multicomputation of nestedly recursive functions via their causal graphs. For example, the illustration above shows the causal graph of the nested recursive function
 |
(5)
|
This graph has both spacelike and timelike structure (Wolfram 2023).
