更新时间：2024-09-21 12:12
递归论，是数理逻辑的一个分支。它是一门研究递归涵数及其推广的学科。递归函数是数论函数的一种，其定义域与值域都是自然数集。只是由于构作函数方法的不同而有别于其他的数论涵数。将定义域推广到不限于自然数集时，便是所谓广义的递归函数。
递归论这门学科最早可以追溯到原始递归式的使用。古代人以及现代的儿童对加法及乘法的理解，实质上就是使用原始递归式。但直到17世纪，法国学者B.巴斯加尔才正式使用与递归式密切相关的数学归纳法。19世纪德国数学家R.戴德金德和意大利的G.皮亚诺正式使用原始递归式，以定义加法与乘法，从而发展了整个自然数论。1923年，T.司寇伦提出并初步证明一切初等数论中的函数都可以由原始递归式作出，即都是原始递归函数。1931年，库尔特·卡塞雷斯在证明其著名的不完全性定理时，以原始递归式为主要工具把所有元数学的概念都算术化了。原始递归函数的重要性遂受到人们的重视，人们开始猜测，原始递归函数可能穷尽一切可计算的函数。但是，德国数学家W.阿克曼的非原始递归的可计算函数的出现，否定了这个猜测，同时也要求人们探讨原始递归函数以外的可计算函数。1934年，哥德尔在J.赫尔布兰德的启示之下，提出了一般递归函数的定义；美国的S.C.克利尼则于1936年证明了这样定义的一般递归函数和A.阿隆佐·邱奇所定义的λ可定义函数是相同的，并给出了几种相等价的定义。这样的一般递归函数后来被称为赫尔布兰德-哥德尔-克利尼定义。1936年，丘奇、A.M.图林各自独立地提出一个论点，即凡可计算的函数都是一般递归函数，这就把递归函数论与能行性论紧紧地结合起来，从而使递归函数的应用范围大大地扩展了（见能行性与一般递归）。关于递归函数本身的进展主要在于定义域的推广，从而得到递归字函数、a递归函数和递归泛涵等等。
递归论研究的函数主要包括本原函数、原始递归函数、递归半函数和递归全函数或称一般递归函数、可摹状函数等等。
处处有定义的函数叫做全函数，未必处处有定义的函数叫做半函数或部分函数。最简单、最基本的函数有三个，即①零函数，,其值永为0；②广义幺函数或射影函数,；③后继函数，。这三个函数的合称就叫做本原函数。
要想由旧函数而作出新函数，必须使用各种各样的算子以及叠置。叠置又名复合或代入，它是最简单、最重要的构造新函数的方法。其一般形式是：由一个 m元函数 f与 m个 n元函数而造成新函数,后者亦可记为。最常见的造新函数的算子是原始递归式。具有n个参数的原始递归式如下：
只有一个参数的原始递归式为：
递归论
其特点是：不能由A、B两函数而直接计算新函数的一般值f(u,x)，而只能依次计算但只要依次计算，必能把任何一个f(u,x) 值都算出来。这就是说，只要A、B为全函数且可计算，则新函数f也是全函数且可计算。
由本原函数出发，经过有限次的叠置与原始递归式而作出的函数叫做原始递归函数。由于本原函数是全函数且可计算，故原始递归函数也是全函数且可计算。原始递归函数所涉及的范围很广，在数论中所使用的数论函数全是原始递归函数。阿克曼却证明了一个不是原始递归的可计算的全函数。经过后人改进后，可表述为如下定义的函数：
这个函数是处处可以计算的。任给 m,n值，如果m为0,可由第一式算出；如果m不为 0而n为0,可由第二式化归为求的值，这时第一变目减少了，如果m,n均不为0，根据第三式可先计算(设为A),再计算，前者g的第二变目减少而第一变目不变，后者则第一变目减少。这样一步步地化归，最后必然化归到第一变目为0，从而可用第一式计算。此外，对任一个一元原始递归函数f(x),都可找出一数a使。这样,就不可能是原始递归函数。
原始递归式的推广，可得到下列有序递归式或半递归式：
它与原始递归式的不同点，在于它不是把的计算化归于f(u,x,)的计算，而是先化归于的计算，然后化归于的计算(可写成f(u,g娾Sx))，再化归于f(u,g咺Sx)的计算，等等。如果有一个m使得g嚲即函数gu在Sx处归宿于0，那末最后化归的f(u,g嚲Sx)的计算，将由第一式知，依次逐步倒退便可以计算了。如果任何 m均使得g嚲，即函数gu在Sx处不归宿于0,将导致永远化归下去而得不到结果。这样，不但不能计算，而且它本身根本没有定义。由此可见，即使A、B与g是处处有定义且可计算的，而由半递归式所定义的函数未必是全函数，也可能是半函数。但只要有定义的地方，即gu归宿于0的地方，就必能计算。
从本原函数出发经过有限次的叠置与半递归式构成的函数叫做递归半函数或递归部分函数，也叫做半递归函数或部分递归函数。这里所提到的“半”、“部分”不是限制“递归”而是限制“函数”的。如果作出的函数是全函数，即其中的gu是处处归宿于 0的，便叫做递归全函数也叫做一般递归函数。递归半函数的特点是，它可能没有定义从而没有值，但只要有值必然可以计算。一般递归函数的特点是，它必处处有定义而且处处可以计算。当递归半函数没有定义时，一般是不知道的。这样，即使把化归于，再化归于如此永远计算下去，也始终得不到其值，并且始终不知道它没有值。但如果另有办法判定递归半函数是否有值，即是否有定义，情况便大不相同。凡是能够判定某个递归半函数是否有值的，该递归半函数叫做潜伏递归函数。对潜伏递归函数永可在有限步内得出其值，或知道它没有值，而与一般递归函数相同。
另一个重要的构造新函数的方法是造逆函数，例如由加法造减法，由乘法造除法等。设已有函数f（u,x）（只写一个参数u）就x解方程可得，这时函数 g 叫做f（作为 x的函数）的逆函数，可记为，至于解一般的方程而得可以看作求逆函数，即三元函数f的逆的推广，解方程可以看作使用求根算子，又叫摹状算子。的最小x根，记为,但当该方程没有根时，则认为, 没有定义。因此，即使f(u,t,x)处处有定义且可计算，但使用摹状算子后所得的函数仍不是全函数，可为半函数。且只要它有定义，那就必然可以计算。如果f(u,t,x) 本身就是半函数，则的意义是：当可计算且其值为0,而时f(u,t,x)均可计算，且其值非0,则指n。此外的情况均作为无定义看待。
由本原函数出发，经过有限次叠置原始递归式与摹状式而构成的函数叫做可摹状函数。可摹状函数一般是部分函数，当摹状算子处处有定义时，它才是全函数。但不管是否全函数，凡可摹状函数有定义的地方都是可计算的。已经证明，可摹状函数与递归半函数是相同的，可摹状的全函数与一般递归函数也是相同的。凡可摹状函数都可以构作一个图林机器（见图林机器理论）计算它，使得当函数有定义时，相应的图林机器必能终止计算并给出其值；当函数没有定义时，相应的机器或者停止并给出没有定义的信号，或者永不停止。由于递归函数可以与其性质这样不同的函数类相等价，因此阿隆佐·邱奇和图林同时提出：可计算函数类恰好是递归函数，可计算的半、全函数分别是递归半、全函数。他们的这个论点现已受到数理逻辑学界的一致赞同，并被当作能行性理论的一个基础。