數理邏輯的一個分支，研究問題類是否存在解的演算法；如果不存在，那麼不可解的程度如何。
在古代中國、希臘就有瞭演算法概念，並且給出瞭演算法的例子。後來古阿拉伯、古印度的人們也著手尋求演算法。中世紀阿拉伯數學傢花拉子米(al-Khowarizmi)在演算法的研究上有突出貢獻，因此現在英文的演算法一詞algo-rithm就是由他的名字得來的。
16世紀，代數裏已出現瞭大量演算法，人們希望在其他領域也能找到到算法。為瞭得到用代數工具描述的幾何證明的算法，R.笛卡兒創造瞭坐標系。為瞭得到判定一切科學命題，起碼是一切數學命題真假的算法，G.W.萊佈尼茨創造瞭數理邏輯。
但是有些問題經過瞭長時期的研究，還是找不到解決它們的算法。例如希爾伯特第10問題，半群上字的問題，謂詞演算中的任一閉合式公式是否為一定理的問題，等等。因此人們懷疑是否這些問題找不到解決它們的算法。為瞭證明解決這些問題的算法不存在，這就要求把算法概念予以精確化，使其能作為數學對象來處理。但是過去數學傢對算法隻有樸素的直觀概念，並無精確的數學定義，因此產生瞭建立算法的精確數學定義的問題。20世紀30年代這個問題才得到解決。出現瞭幾個等價的精確的數學定義。其中最重要的有遞歸函數、圖靈機、正規算法，等等。
K.哥德爾受到瞭J.埃爾佈朗的啟發在一次介紹他的著名的不完備性定理時提出瞭給予算法以精確定義的方法。S.C.克林進一步把它具體化，建立瞭等式演算從而定義瞭遞歸函數。不久又證明瞭遞歸函數和λ─可定義函數的等價性。在歐洲A.M.圖靈也引進瞭著名的圖靈機來描繪算法。繼而也證明瞭圖靈可計算函數和遞歸函數的等價性。在知道圖靈機以前，A.丘奇就認為遞歸函數或λ─可定義函數是算法可計算函數的精確數學描述。但是由於算法不是精確的數學概念，無法證明二者的等價性，因此丘奇建立瞭丘奇論題，斷言一切算法可計算函數都是遞歸函數，即二者是等價的。克林曾懷疑存在非遞歸的算法可計算函數，在多次企圖建立反例遭到失敗後，他才接受瞭丘奇論題。由於圖靈機的定義很符合人們對算法的直觀經驗，因此哥德爾在見到圖靈機的定義後也接受瞭丘奇論題。
遞歸函數產生後，開始瞭遞歸論的發展。因此遞歸論的產生是幾千年數學發展的結果。隨著計算機的發展，人們要有在符號串上直接定義算法。60年代初出現瞭幾個等價的定義，其中胡世華最早發表瞭遞歸算法。
遞歸論中另一個重要概念是算法可產生集的精確描述遞歸可枚舉集。可以證明一切遞歸集，即算法可判定集，都是遞歸可枚舉集。但是存在不是遞歸集的遞歸可枚舉集。由於許多數學問題，例如上面講的長期未能找出算法的問題，都可以化為某個遞歸可枚舉集是否遞歸集的問題。因此非遞歸的遞歸可枚舉集的研究就幫助人們證明瞭希爾伯特第10問題、半群上字的問題、謂詞演算任意命題閉合式公式是否定理的判定問題等等都是不存在算法解的。從而解決瞭一批長期未能解決的問題。
既然有不能存在判定算法的遞歸可枚舉集，那麼自然會提出是否一切這種遞歸可枚舉集的不可解的程度是一樣的。這就需要對不可解的程度給出度量的辦法。1944年E.L.波斯特提出不可解度的概念，並且提出瞭著名的波斯特問題。1953年波斯特和克林企圖解決波斯特問題，雖然沒有解決它，但是創造瞭帶信息源的遞歸構造辦法。後來這方法有很大的發展。例如證明瞭極小度的存在性定理（見不可解度），以及關於一些結構在度結構內的嵌入的結果。1957年R.M.弗裡德貝格和A.A.穆切尼克各自獨立地創造瞭有窮損害優先方法解決瞭波斯特問題。這一強有力的方法出現後，遞歸論進入瞭一個新的階段。現在有窮損害優先方法也稱為O′-優先方法。60年代J.R.休恩菲爾德和G.E.薩克斯各自獨立地創造瞭無窮損害優先方法，又稱O″-優先方法。前者是為瞭證明厚性引理；而後者證明瞭遞歸可枚舉度的稠密性定理。70年代A.H.拉克倫創造瞭O‴-優先方法，這方法比無窮損害方法更為有力。除瞭上述方法外，構造遞歸可枚舉極小對的預測方法，構造極大集的e-狀態方法，樹形構造法等也都是遞歸論研究中的重要工具。
隨著集合論的發展，遞歸論也向廣義遞歸論發展。序數上遞歸論對有窮概念的推廣在無窮語言中得到瞭重要應用。自然數上遞歸論已在許多方面得到應用。
隨著計算機的發展，要求把古典數學能行化。以A.尼羅德為首的遞歸論學傢開拓瞭遞歸數學的研究領域。他們把古典數學的基本概念算法化，然後考慮哪些數學定理可以成立哪些無法成立。遞歸論在計算機科學裡的應用主要是用於計算復雜性理論。起初是把圖靈機作為研究計算復雜性的模型考慮計算的時間、空間復雜性。繼而基於遞歸論，再加上適當的公理又建立瞭抽象計算復雜性理論。近年來遞歸論的方法大量地用於 P與NP問題的研究中。