在可計算性理論中，原始遞歸函數粗略地說就是一個可以被計算機程序計算的函數，其循環都是for循環（即在進入循環之前可以確定每個循環的迭代次數的上限） . 原始遞歸函數構成那些也是全函數的一般遞歸函數的嚴格子集。

原始遞歸函數的重要性在于這樣一個事實，即在數論（以及更普遍的數學）中研究的大多數可計算函數都是原始遞歸函數。 例如，加法和除法、階乘和指數函數以及返回第 n 個素數的函數都是原始遞歸的。 事實上，為了證明一個可計算函數是原始遞歸的，只要證明它的時間復雜度受輸入大小的原始遞歸函數的限制就足夠了。 因此，設計一個非原始遞歸的可計算函數并不容易； 下面的§ 限制部分顯示了一些示例。

這組原始遞歸函數在計算復雜性理論中被稱為 PR。

原始遞歸函數采用固定數量的參數，每個參數都是自然數（非負整數：{0, 1, 2, ...}），并返回一個自然數。 如果它有 n 個參數，它被稱為 n-ary。

這些公理給出了基本的原始遞歸函數：

• 常數函數ck_{n: 對于每個自然數n和每個k，定義的k元常數函數 通過 C n k ( x 1 , … , x k ) = d e f n {\displaystyle C_{n}{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n} ，是原始遞歸。}
• 后繼函數：一元后繼函數 S，它返回其參數的后繼（見 Peano 假設），即 S ( x ) = d e f x + 1 {\displaystyle S(x)\ { \stackrel {\mathrm {def} }{=}}\ x+1} ，是原始遞歸。
• 投影函數 P i k {\displaystyle P_{i}{k}} ：對于所有自然數 i , k {\displaystyle i,k} 使得 1 ≤ i ≤ k {\displaystyle 1\leq i\leq k} ，由 P i k ( x 1 , … , x k ) = d e f x i {\displaystyle P_{i}{k}(x_{1},\ldots ,x_{ k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}} 是原始遞歸。

通過應用這些公理給出的操作可以獲得更復雜的原始遞歸函數：

• 復合運算符 ° {\displaystyle \circ \,}（也稱為替換運算符）：給定一個多元函數 h ( x 1 , … , x m ) {\displaystyle h(x_{1} ,\ldots ,x_{m})\,} 和 m 個 k 元函數 g 1 ( x 1 , … , x k ) , … , g m ( x 1 , … , x k ) {\displaystyle g_{1} (x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})} : h ° ( g 1 , … , g m ) = d e f f，其中 f ( x 1 , … , x k ) = h ( g 1 ( x 1 , … , x k ) , … , g m (x 1 , … , x k )) 。 {\displaystyle h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad { text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ ldots ,g_{m}(x_{1},\ldots ,x_{k})).}

• 原始遞歸運算符 ρ：給定 k 元函數 g ( x 1 , … , x k ) {\displaystyle g(x_{1},\ldots ,x_{k})\,} 和 ( k + 2)-ary 函數 h ( y , z , x 1 , … , x k ) {\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,} : ρ ( g , h ) = d e f f ，其中 ( k + 1 ) 元函數 f 由 f ( 0 , x 1 , … , x k ) = g ( x 1 , … , x k ) f ( S ( y ) , x 1 , … , x k ) = h ( y , f ( y , x 1 , … , x k ) , x 1 , … , x k ) 。 {\displaystyle {\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text {其中 }}(k+1){\text{-ary 函數 }}f{\text{ 由}}\\f(0,x_{1},\ldots ,x_{ k})&=g(x_{1},\ldots,x_{k})\\f(S(y),x_{1},\ldots,x_{k})&= h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k}).\end{aligned}}}解釋：函數 f 充當從 0 到xxx個參數值的 for 循環。 f 的其余參數（此處用 x1、...、xk 表示）是 for 循環的一組初始條件，可在計算期間使用但不可更改。 定義 f 的方程式右側的函數 g 和 h 代表執行計算的循環體。 函數 g 僅用于執行初始計算一次。 循環的后續步驟的計算由 h 執行。 h 的xxx個參數是 for 循環索引的當前值。 h 的第二個參數是來自前面步驟的 for 循環先前計算的結果。 h 的其余參數是前面提到的 for 循環的不可變初始條件。 它們可能會被 h 用來執行計算，但它們本身不會被 h 更改。