递归论，又被称为可计算性理论，是数学的一个分支。它主要研究可计算性和可定义性的数学理论及其分层。
递归函数起源于20世纪30年代，那时歌德尔、丘奇、图灵、克林和波斯特等人在研究自然数集合的可计算性。虽然大部分自然数集合都是不可计算的，但我们可以对这些不可计算的集合进行复杂性比较。图灵归约就是一种典型的比较方式，这些比较可以看作一种广义上的分层。递归论专注于这些比较方式及其产生的代数结构。
这些比较方式产生的代数结构研究逐渐发展成了度论。其中，图灵度的研究最为广泛。它的研究可以追溯到克林和波斯特的早期工作，之后经过众多学者的长期积累，如克林、弗莱德贝格、斯佩克特、萨克斯等人，他们引入了多种构造图灵度的方法。
到了20世纪80年代，图灵度结构研究开始转向更广泛的研究领域，主要集中在图灵度结构模型论的性质和理论的可判定性上。其中，图灵度结构理论和二阶算术的递归同构性被揭示出来，这是由辛普森在1977年证明的，从而揭示了图灵度结构理论的复杂性。关于图灵度结构的模型论性质还有两大重要且困难的问题：一是图灵跃变是否能在一般图灵结构中定义；二是是否存在非平凡自同构的图灵度。第一个问题已由思莱曼和肖尔在1999年解决，而第二个问题仍然具有挑战性。近年来，思莱曼和武丁证明了图灵度的结构群最多只是可数。
递归函数图灵度结构问题是这一领域备受关注的课题之一。它源于波斯特关于是否存在介于递归集和停机问题的递归函数可列举图灵度的问题。这一问题得到了穆奇尼克和弗莱德贝格的确切答案，他们引入的有穷损害方法已成为这一领域的基本工具之一。在20世纪80年代，研究课题开始转向递归可枚举图灵度模型论的结构理论。例如，哈林顿和谢拉赫证明了递归可枚举图灵度结构的理论是不可判定的。多位学者用不同的编码方法证明了递归可枚举图灵度的理论和一阶算术理论是递归同构的。
广义递归论研究一般数学的可计算性和可定义性。有两种方式可以推广经典的递归论：一种是将图灵机推广到实数或序数上，研究相应集合的可计算性；另一种是通过研究可定义性来推广。博雷尔集作为超算术实数集的“相对化”，可以被视为广义递归论集合的一个例子。现在，递归论更多地关注在其他学科的应用，如递归模型论、反推数学、算法随机性理论等领域。
