術語“遞迴函式”通常在非正式場合用於描述任何用遞迴定義的函式。對於這個非正式的定義，有幾個正式的對應物，其中許多隻在細微之處有所不同。
Kleene (1952) 將“偏遞迴函式”定義為非負整數的任何函式 
，它是由一個非矛盾的方程組定義的，其左右兩邊由以下組成：(1) 函式符號（例如，
, 
, 
, 等等），(2) 非負整數的變數（例如，
, 
, 
, 等等），(3) 常數 0，以及 (4) 後繼函式 
。
例如，
 |  |  |
(1)
|
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
定義 
為函式 
，它計算 
和 
的乘積。
請注意，方程可能無法唯一確定每個可能輸入的 
值，從這個意義上說，定義是“偏的”。如果方程組確定了每個輸入的 f 值，那麼該定義就被稱為“全的”。當單獨使用術語“遞迴函式”時，通常隱含的是指“全遞迴函式”。請注意，一些作者使用術語“廣義遞迴函式”來表示偏遞迴函式，儘管另一些作者使用它來表示“全遞迴函式”。
以這種方式遞迴定義的函式集已知等同於由圖靈機和lambda 演算計算的函式集。
Wolfram (2023) 討論了巢狀遞迴函式透過其因果圖的多重計算。例如，上面的插圖顯示了巢狀遞迴函式的因果圖
 |
(5)
|
該圖具有類空間和類時間結構 (Wolfram 2023)。
