术语“递归函数”通常在非正式场合用于描述任何用递归定义的函数。对于这个非正式的定义，有几个正式的对应物，其中许多只在细微之处有所不同。
Kleene (1952) 将“偏递归函数”定义为非负整数的任何函数 
，它是由一个非矛盾的方程组定义的，其左右两边由以下组成：(1) 函数符号（例如，
, 
, 
, 等等），(2) 非负整数的变量（例如，
, 
, 
, 等等），(3) 常数 0，以及 (4) 后继函数 
。
例如，
 |  |  |
(1)
|
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
定义 
为函数 
，它计算 
和 
的乘积。
请注意，方程可能无法唯一确定每个可能输入的 
值，从这个意义上说，定义是“偏的”。如果方程组确定了每个输入的 f 值，那么该定义就被称为“全的”。当单独使用术语“递归函数”时，通常隐含的是指“全递归函数”。请注意，一些作者使用术语“广义递归函数”来表示偏递归函数，尽管另一些作者使用它来表示“全递归函数”。
以这种方式递归定义的函数集已知等同于由图灵机和lambda 演算计算的函数集。
Wolfram (2023) 讨论了嵌套递归函数通过其因果图的多重计算。例如，上面的插图显示了嵌套递归函数的因果图
 |
(5)
|
该图具有类空间和类时间结构 (Wolfram 2023)。
