递归论用语。令A⊆Nⁿ，如果A的特徵函式C_A(x₁，…，x_n)是μ-递归函式，则称A为递归集。

递归集是具有能行可计算的自然数集。设A为自然数集合，若其特徵函式C_A是递归函式，则称A为递归集。对递归集合A，为了判定某个自然数n是否属于A，只要计算其特徵函式C_A在n处的值C_A(n)即可。由于C_A的递归性，上述过程可能行地完成，从而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(x₁，…x_n)=x_i;

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

再介绍几个将函式变换为函式的运算元。

(1)複合运算元 设f是n元函式，g₁…g_n是m元函式，複合运算元将f，g₁…g_n变换成为如下的m元函式h：

h(x₁…xm)=f₁g₁(x₁，…x_m)，…g_n(x₁，…x_m))

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

h(x₁，…，x_n，0)=f(x₁，…x_n)

h(x₁，…x_n，y+1)=g(x₁，…x_n，y，h(x₁，…xn))

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

h(x₁，…xn)=μyf(x₁…x_ny)

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

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

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

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

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

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