递归集合

在C语言中，位段的声明和结构（struct）类似，但它的成员是一个或多个位的字段，这些不同长度的字段实际储存在一个或多个整型变量中。在声明时，位段成员必须是整形或枚举类型（通常是无符号类型），且在成员名的后面是一个冒号和一个整数，整数规定了成员所占用的位数。位域不能是静态类型。不能使用&对位域做取地址运算，因此不存在位域的指针，编译器通常不支持位域的引用（reference）。

定义自然数的子集S被称为递归的，如果存在一个全可计算函数

使得

换句话说，集合S是递归的，当且仅当指示函数 是可计算的。

例子空集

自然数

自然数的所有有限子集（有限子集并非可数子集，后者可能有无限多的元素）

素数的集合

递归语言是在形式语言字母表之上所有可能词的集合中的递归集合。

性质如果A是递归集合，则A的补集是递归集合。 如果A和B是递归集合，则A∩B、A∪B和A×B是递归集合。集合A是递归集合，当且仅当A和A的补集是递归可枚举集合。一个递归集合在全可计算函数下的原像（preimage）是递归集合1。

递归函数一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的。

古典递归函数，是一种定义在自然数集合上的函数，它的未知值往往要通过有限次运算回归到已知值来求出，故称为“递归”。它是古典递归函数论的研究对象

递归可枚举集合递归可枚举集，又称部分递归集。在能行性理论中，基本概念是递归函数，它可刻画为：任给x，只要它在x处有定义必可在有限步骤内求出其值。因此递归全函数（即处处有定义的）必可在有限步骤内求出它的任一值，至于递归部分函数（未必处处有定义的）则只要求有定义处可求出其值，但不要求能够在有限步骤内判定它的定义域的元素，即对任给的x判定x是否属于函数的定义域。

本词条内容贡献者为:

李华青 - 副教授 - 西南大学电子信息工程学院