數論函數的一種，其定義域與值域都是自然數集，隻是由於構作函數方法的不同而有別於其他的函數。處處有定義的函數叫做全函數，未必處處有定義的函數叫做部分函數。最簡單又最基本的函數有三個：零函數O(x)=0(其值恒為0)；射影函數

；後繼函數 >S( x)= x+1。它們合稱初始函數。要想由舊函數作出新函數，必須使用各種算子。

　　代入（又名復合或疊置）是最簡單又最重要的造新函數的算子，其一般形狀是：由一個m元函數f與m個n元函數g1，g2，…，gm造成新函數f(g1(x1，x2，…，xn)，g2(x1，x2，…，xn)，…，gm(x1，x2，…，xn))，亦可記為f(g1，g2，…，gm)(x1，x2，…，xn)。另一個造新函數的算子是原始遞歸式。具有n個參數u1，u2，…，un的原始遞歸式為：

具有一個參數的原始遞歸式可簡寫為：

其特點是，不能由 g、 h兩函數直接計算新函數的一般值 f( u， x)，而隻能依次計算 f( u，0)， f( u，1)， f( u，2)，…；但隻要依次計算，必能把任何一個 f( u， x)值都算出來。換句話說隻要 g， h為全函數且可計算，則新函數f也是全函數且可計算。

　　由初始函數出發，經過有限次的代入與原始遞歸式而作出的函數叫做原始遞歸函數。由於初始函數顯然是全函數且可計算，故原始遞歸函數都是全函數且可計算。通常使用的數論函數全是原始遞歸函數，可見原始遞歸函數是包括很廣的。但是W.阿克曼證明瞭，可以作出一個可計算的全函數，它不是原始遞歸的。經過後人改進後，這個函數可寫為如下定義的阿克曼函數：

容易看出，這個函數是處處可計算的。任給 m， n的值，如果 m為0，可由第一式算出；如果 m不為0而 n為0，可由第二式化歸為求 g( m，1)的值，這時第一變目減少瞭；如果 m， n均不為0，根據第三式可先計算 g( m， n-1)，設為 α，再計算 g( m-1， α)，前者第二變目減少（第一變目不變），後者第一變目減少。極易用歸納法證得，這樣一步一步地化歸，最後必然化歸到第一變目為0，從而可用第一式計算。所以這個函數是處處可計算的。此外又容易證明，對任何一個一元原始遞歸函數 f( x)，永遠可找出一數 α使得 f( x)＜ g( α， x)。這樣， g( x， x)+1便不是原始遞歸函數，否則將可找出一數 b使得 g( x， x)+1＜ g( b， x)。令 x= b，即得 g( b， b)+1＜ g( b， b)，而這是不可能的。

　　另一個重要的造新函數的算子是造逆函數的算子，例如，由加法而造減法，由乘法造除法等。一般，設已有函數f(u，x)，就x解方程f(u，x)=t，可得x=g(u，t)。這時函數g叫做f的逆函數。至於解一般方程f(u，t，x)=0而得x＝g(u，t)可以看作求逆函數的推廣。解方程可以看作使用求根算子。f(u，t，x)=0的最小x根（如果有根的話），記為μx[f(u，t，x)=0]。當方程沒有根時，則認為μx[f(u，t，x)=0]沒有定義。可見，即使f(u，t，x)處處有定義且可計算，但使用求根算子後所得的函數μx[f(u，t，x)=0]仍不是全函數，可為部分函數。但隻要它有定義，那就必然可以計算。這算子稱為μ算子。如果f(u，t，x)本身便是部分函數，則μx[f(u，t，x)=0]的意義是：當f(u，t，n)可計算且其值為0，而x＜n時f(u，t，x)均可計算而其值非0，則μx[f(u，t，x)=0]指n；其他情況則作為無定義。例如，如果f(u，t，x)=0根本沒有根，或者雖然知道有一根為n，但f(u，t，n-1)不可計算，那麼μx[f(u，t，x)=0]都作為沒有定義。在這樣定義後，隻要μx[f(u，t，x)=0]有值便必可計算。由初始函數出發，經過有窮次使用代入、原始遞歸式與μ算子而作成的函數叫做部分遞歸函數，處處有定義的部分遞歸函數稱為全遞歸函數，或一般遞歸函數。

　　原始遞歸函數類裡還有一個重要的子類稱為初等函數類，它是由非負整數與變元經過有窮次加、算術減（即｜α-b｜）、乘、算術除

、疊加Σ、疊乘П而得的函數組成的類。

　　波蘭人A.格熱高契克把原始遞歸函數類按定義的復雜程度來分類，稱為格熱高契克分層或波蘭分層。

　　要把遞歸函數應用於謂詞，首先要定義謂詞的特征函數。謂詞R(x，y)的特征函數是

稱謂詞 R是遞歸謂詞，若 R的特征函數是遞歸函數；稱自然數子集 A為遞歸集，若謂詞 x∈ A是遞歸謂詞。有瞭上述定義，就可以用遞歸函數來處理遞歸謂詞和遞歸集。為瞭處理 N× N（其中 N為自然數集）的子集，就要建立配對函數，所謂配對函數通常是指由 N× N到 N的一個函數 f( x， y)與它的逆函數 g 1( z)， g 2( z)。它們都滿足以下關系：

　　可以構造許多原始遞歸的配對函數。

　　遞歸函數也可以用來處理符號串。處理的辦法是對符號及符號串配以自然數。這方法是K.哥德爾開始引進的，因此稱為哥德爾配數法。例如，在要處理的符號系統｛α1，α2，α3，…｝中，可以用奇數1，3，5，7，…作為α1，α2，α3，α4，…的配數，符號串

以 為其配數，其中 P s是第 s個素數， n ij是 α ij的配數。這種配數稱為哥德爾配數。有瞭哥德爾配數法，就可以用遞歸函數來描寫、處理有關符號串的謂詞瞭。