[拼音]：diguilun
[外文]：recursion theory
数理逻辑的一个分支，研究问题类是否存在解的算法；如果不存在，那么不可解的程度如何。
在古代中国、希腊就有了算法概念，并且给出了算法的例子。后来古阿拉伯、古印度的人们也着手寻求算法。中世纪阿拉伯数学家花拉子米(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问题的研究中。
