递归集是递归论用语。令A⊆Nn，如果A的特征函数CA(x1，…，xn)是μ-递归函数，则称A为递归集。

递归论用语。令A⊆Nn，如果A的特征函数CA(x1，…，xn)是μ-递归函数，则称A为递归集。

递归集是具有能行可计算的自然数集。设A为自然数集合，若其特征函数CA是递归函数，则称A为递归集。对递归集合A，为了判定某个自然数n是否属于A，只要计算其特征函数CA在n处的值CA(n)即可。由于CA的递归性，上述过程可能行地完成，从而n是否属于A是能行可判定的。∅，N都是递归集，而且任何有穷集也都是递归的。此外，递归集类关于集合的交、并、补运算都是封闭的。

又称“递归函数论”、“能行性理论”，指主要用数学方法研究“可构造性”、“能行可计算性”或“能行过程”的学科。各种递归函数本身的构造也是它研究的重要方面。它既属于数理逻辑的一个分支学科，不属于基础数学的一个分支学科。

递归论的主要内容包括原始递归函数，一般递归函数，部分递归函数，递归可枚举性，判定问题，递归不可解理理论，a可递归论，碾系理论等。

递归论的主要方法是通过对数论函数的研究，揭示能行过程的本质，从而解决许多重要的数学问题。

递归论对数论函数的研究从原始递归函数开始，进而推广为一般递归函数，并发现一般递归函数与能行可计算函数是可以相互定义的，凡是有一个计算过程或一个算法可以将函数值计算出来的函数都是一般递归函数。

递归论所研究的数论函数都有精确的数学定义，定义是以递归的方式进行的。例如，用递归定义方式定义“斐博那奇函数”如下：

f(0)=0

f(1)=1

f(n+2)=f(n)+f(n+1)

通过上面的定义，对任意一个自然数n，f(n)恒可使用上述步骤逐步地取得。

在历史上，对于“能行过程”这一含糊的概念有过许多定义，如一般递归式、图灵机器、正规算法、有限自动机等。通过递归论的研究，发展这些定义彼此都是等价的。从这点可以看出，深入研究递归论对于弄清“能行过程”是十分关键的。

在这一领域里作出重要贡献的有希尔伯特、哥德尔、邱吉、图灵、克林尼、波斯特等人。

递归论不仅在数学基础的研究方面有极其重要的应用，而且在许多新兴的科学，尤其在电子计算机科学中愈来愈显示出它的重要性。

概率论中引进的最重要的变换。概率论中的许多问题，尤其那些连系着独立随机变数求和的问题，可以借助特征函数得出简单的解法。这种函数变换理论最初由法国数学家Fourier引进，在许多数学分支中起了重大作用。特征函数在解决概率论中著名的“大数定律”及“中心极限定理”时起了举足轻重的作用。

在概率论中，任何随机变量的特征函数(缩写：ch.f,复数形式：ch.f's)完全定义了它的概率分布。

特征函数具有以下基本性质：

如果两个随机变量具有相同的特征函数，那么它们具有相同的概率分布； 反之， 如果两个随机变量具有相同的概率分布， 它们的特征函数也相同(显然)。

独立随机变量和的特征函数等于每个随机变量特征函数的乘积。

函数的概念是一个很一般的概念。在定义函数时，不一定要具体给出通过自变量求函数值的方法。因此，可将函数分成两类，一类是所谓能行可计算函数，另一类是非能行可计算的函数。这前一种函数无论在理论上或在实际上都是非常重要的，因此人们便试图给它们以精确的数学刻画。递归函数便是许多这种刻画中的一种。

我们以下考虑的函数都是从自然数到自然数的函数。

我们先定义几个初等函数：

(1)零函数 Z(x)=0;

(2)后继函数 S(x)=x+1;

(3)广义幺函数 U1n(x1，…xn)=xi;

显然，上面这些函数都是能行可计算的。

再介绍几个将函数变换为函数的算子。

(1)复合算子 设f是n元函数，g1…gn是m元函数，复合算子将f，g1…gn变换成为如下的m元函数h：

h(x1…xm)=f1g1(x1，…xm)，…gn(x1，…xm))

(2)递归算子 设f是n元函数 (≥0)，g是n+2元函数，递归算子将f，g变换成满足下列条件的h+1元函数h：

h(x1，…，xn，0)=f(x1，…xn)

h(x1，…xn，y+1)=g(x1，…xn，y，h(x1，…xn))

(3)μ一算子，设f是n+1元函数，如果存在y，使f(x1，…xn，y)=0，我们以μyf(x1…xny)表示这样的y中的最小者，如果使f(x1…xny)=0的y不存在，我们说μyf(x1，…xny)无定义。μ-算子将n+1元函数f变换成下面的几元函数h

h(x1，…xn)=μyf(x1…xny)

注意，μ算子可以将一个全函数变换成一个部分函数(即在自然数的某个子集上有定义的函数)。

可以看出，上述所有算子都是将能行可计算函数变换为能行可计算函数。

所谓递归函数类便是包含零函数、广义幺函数，并在复合算子、递归算子，μ-算子下封闲的最小函数类。

容易相信，任何递归函数都是能行可计算的。反过来，是否存在直观上能行可计算的，但不是递归的函数呢?人们直到现在还没有发现这样的函数。相反，人们证明了，现已遇到的直观上能行可计算的函数都是递归函数。进一步，人们还证明了，递归函数类与其他的一些刻画能行可计算函数的方法产生的函数类是完全一致的，这些事实促使车尔赤(Church)提出了他的著名的论点：

递归函数类与直观能行可计算函数类是重合的。

这个论点已被大多数递归论学者所接受。