原始遞迴函式

正如 Meyer 和 Ritchie (1967) 首次展示的那樣，do 迴圈（具有固定的迭代限制）是 while 迴圈的特例。僅使用 do 迴圈即可實現的函式稱為原始遞迴函式。（相比之下，可計算函式 可以使用 for 迴圈和 while 迴圈的組合，或僅使用 while 迴圈進行編碼。）原始遞迴函式的示例包括 冪、最大公約數 和 （給出第 個 素數 的函式）。

阿克曼函式 是 良定義 全函式 的最簡單示例，它是 可計算的 但不是原始遞迴的，這為 1900 年代初期認為每個 可計算函式 也都是原始遞迴函式的觀點提供了反例 (Dötzel 1991; Wolfram 2002, p. 907)。