數理邏輯的一個分支。它是一門研究遞迴涵數及其推廣的學科。遞迴函數是數論函數的一種，其定義域與值域都是自然數集。隻是由於構作函數方法的不同而有別於其他的數論涵數。將定義域推廣到不限於自然數集時，便是所謂廣義的遞迴函數。
歷史 遞迴論這門學科最早可以追溯到原始遞迴式的使用。古代人以及現代的兒童對加法及乘法的理解，實質上就是使用原始遞迴式。但直到17世紀，法國學者B.巴斯加爾才正式使用用與遞歸式密切相關的數學歸納法。19世紀德國數學傢R.戴德金德和意大利的G.皮亞諾正式使用原始遞歸式，以定義加法與乘法，從而發展瞭整個自然數論。1923年，T.司寇倫提出並初步證明一切初等數論中的函數都可以由原始遞歸式作出，即都是原始遞歸函數。1931年，K.哥德爾在證明其著名的不完全性定理時，以原始遞歸式為主要工具把所有元數學的概念都算術化瞭。原始遞歸函數的重要性遂受到人們的重視，人們開始猜測，原始遞歸函數可能窮盡一切可計算的函數。但是，德國數學傢W.阿克曼的非原始遞歸的可計算函數的出現，否定瞭這個猜測，同時也要求人們探討原始遞歸函數以外的可計算函數。1934年，哥德爾在J.赫爾佈蘭德的啟示之下，提出瞭一般遞歸函數的定義；美國的S.C.克利尼則於1936年證明瞭這樣定義的一般遞歸函數和A.丘奇所定義的λ可定義函數是相同的，並給出瞭幾種相等價的定義。這樣的一般遞歸函數後來被稱為赫爾佈蘭德-哥德爾-克利尼定義。1936年，丘奇、A.M.圖林各自獨立地提出一個論點，即凡可計算的函數都是一般遞歸函數，這就把遞歸函數論與能行性論緊緊地結合起來，從而使遞歸函數的應用范圍大大地擴展瞭（見能行性與一般遞歸）。關於遞歸函數本身的進展主要在於定義域的推廣，從而得到遞歸字函數、a遞歸函數和遞歸泛涵等等。
基本內容 遞歸論研究的函數主要包括本原函數、原始遞歸函數、遞歸半函數和遞歸全函數或稱一般遞歸函數、可摹狀函數等等。
本原函數 處處有定義的函數叫做全函數，未必處處有定義的函數叫做半函數或部分函數。最簡單、最基本的函數有三個，即①零函數，O(x)=0，其值永為0；②廣義么函數或射影函數，Imn(x1，…，xm) =xn(1≤n≤m)；③後繼函數，Sx(=x+1)。這三個函數的合稱就叫做本原函數。
要想由舊函數而作出新函數，必須使用各種各樣的算子以及疊置。疊置又名復合或代入，它是最簡單、最重要的構造新函數的方法。其一般形式是：由一個 m元函數f與 m個 n元函數g1，g2，…，gm而造成新函數f[g1(x1，…，xn)，g2(x1，…，xn)，…，gm(x1，…，xn)]，後者亦可記為f(g1，…，gm)(x1，…，xn)。最常見的造新函數的算子是原始遞歸式。具有n個參數的原始遞歸式如下：
隻有一個參數的原始遞歸式為：
其特點是：不能由A、B兩函數而直接計算新函數的一般值
f(u，x)，而隻能依次計算
f(u，0)，
f(u，1)，
f(u，2)，…。但隻要依次計算，必能把任何一個
f(u，x) 值都算出來。這就是說，隻要A、B為全函數且可計算，則新函數f也是全函數且可計算。
原始遞歸函數 由本原函數出發，經過有限次的疊置與原始遞歸式而作出的函數叫做原始遞歸函數。由於本原函數是全函數且可計算，故原始遞歸函數也是全函數且可計算。原始遞歸函數所涉及的范圍很廣，在數論中所使用的數論函數全是原始遞歸函數。阿克曼卻證明瞭一個不是原始遞歸的可計算的全函數。經過後人改進後，可表述為如下定義的函數：
這個函數是處處可以計算的。任給 m，n值，如果m為0，可由第一式算出；如果m不為0而n為0，可由第二式化歸為求
g(m，1)的值，這時第一變目減少瞭，如果m，n均不為0，根據第三式可先計算
g(m，n-1)(設為A)，再計算
g(m-1，A)，前者
g的第二變目減少而第一變目不變，後者則第一變目減少。這樣一步步地化歸，最後必然化歸到第一變目為0，從而可用第一式計算。此外，對任一個一元原始遞歸函數
f(x)，都可找出一數a使
f(x)＜
g(
a，x)。這樣，
g(
x，x)+1就不可能是原始遞歸函數。
原始遞歸式的推廣，可得到下列有序遞歸式或半遞歸式：
它與原始遞歸式的不同點，在於它不是把f(u，Sx)的計算化歸於f(u，x，)的計算，而是先化歸於f(u，g(u，Sx))的計算，然後化歸於f[u，g(u，g(u，Sx))]的計算(可寫成f(u，gn2Sx))，再化歸於f(u，gu3Sx)的計算，等等。如果有一個m使得gumSx=0即函數gu在Sx處歸宿於0，那末最後化歸的f(u，gumSx)的計算，將由第一式知f(u，0)=A(u)，依次逐步倒退便可以計算f(u，x)瞭。如果任何 m均使得gumSx≠0，即函數gu在Sx處不歸宿於0，將導致永遠化歸下去而得不到結果。這樣，不但不能計算f(u，Sx)，而且它本身根本沒有定義。由此可見，即使A、B與g是處處有定義且可計算的，而由半遞歸式所定義的函數未必是全函數，也可能是半函數。但隻要有定義的地方，即gu歸宿於0的地方，就必能計算。
遞歸半函數和遞歸全函數 從本原函數出發經過有限次的疊置與半遞歸式構成的函數叫做遞歸半函數或遞歸部分函數，也叫做半遞歸函數或部分遞歸函數。這裡所提到的“半”、“部分”不是限制“遞歸”而是限制“函數”的。如果作出的函數是全函數，即其中的gu是處處歸宿於0的，便叫做遞歸全函數也叫做一般遞歸函數。遞歸半函數的特點是，它可能沒有定義從而沒有值，但隻要有值必然可以計算。一般遞歸函數的特點是，它必處處有定義而且處處可以計算。當遞歸半函數沒有定義時，一般是不知道的。這樣，即使把f(u，Sx)化歸於f(u，gu，Sx)，再化歸於f(u，gu2Sx)，…，如此永遠計算下去，也始終得不到其值，並且始終不知道它沒有值。但如果另有辦法判定遞歸半函數是否有值，即是否有定義，情況便大不相同。凡是能夠判定某個遞歸半函數是否有值的，該遞歸半函數叫做潛伏遞歸函數。對潛伏遞歸函數永可在有限步內得出其值，或知道它沒有值，而與一般遞歸函數相同。
另一個重要的構造新函數的方法是造逆函數，例如由加法造減法，由乘法造除法等。設已有函數f（u，x）（隻寫一個參數u）就x解方程f(u，x)=t可得x=g(u，t)，這時函數g叫做f（作為 x的函數）的逆函數，可記為g(u，t) =fu-1(t)，至於解一般的方程f(u，t，x) =0而得x=g(u，t)，可以看作求逆函數，即三元函數f的逆的推廣，解方程可以看作使用求根算子，又叫摹狀算子。f(u，t，x)=0的最小x根，記為u∝[f(u，t，x) =0]，但當該方程沒有根時，則認為u∝[f(u，t，x) =0]，沒有定義。因此，即使f(u，t，x)處處有定義且可計算，但使用摹狀算子後所得的函數u∝[f(u，t，x) =0]仍不是全函數，可為半函數。且隻要它有定義，那就必然可以計算。如果f(u，t，x)本身就是半函數，則u∝[f(u，t，0) =0]的意義是:當f(u，t，x)可計算且其值為0，而x＜n時f(u，t，x)均可計算，且其值非0，則u∝[f(u，t，x) =0]指n。此外的情況均作為無定義看待。例如，f(u，t，x) =0根本沒有x根，或者雖然知道有一根為n，但f(u，t，n-1)不可計算，這時u∝[f(u，t，0) =0]都作為沒有定義。
可摹狀函數 由本原函數出發，經過有限次疊置原始遞歸式與摹狀式而構成的函數叫做可摹狀函數。可摹狀函數一般是部分函數，當摹狀算子處處有定義時，它才是全函數。但不管是否全函數，凡可摹狀函數有定義的地方都是可計算的。已經證明，可摹狀函數與遞歸半函數是相同的，可摹狀的全函數與一般遞歸函數也是相同的。凡可摹狀函數都可以構作一個圖林機器（見圖林機器理論）計算它，使得當函數有定義時，相應的圖林機器必能終止計算並給出其值；當函數沒有定義時，相應的機器或者停止並給出沒有定義的信號，或者永不停止。由於遞歸函數可以與其性質這樣不同的函數類相等價，因此丘奇和圖林同時提出:可計算函數類恰好是遞歸函數，可計算的半、全函數分別是遞歸半、全函數。他們的這個論點現已受到數理邏輯學界的一致贊同，並被當作能行性理論的一個基礎。