在数学、逻辑和计算机科学中，如果一种形式语言(从固定字母表中取出的一组符号集合组成的有限序列)，是该语言字母表中所有可能有限序列集合的递归子集，那么它就被称为递归语言。同样地，如果有一种通用图灵机(一旦遇到给定输入就进入停止状态的图灵机)，当输入一个有限符号序列时，如果该序列属于该语言，图灵机就进入接受状态，反之它就进入拒绝状态，那么这个形式语言也是递归的。递归语言也被称为可判定语言。
可判定性这种概念可以扩展到其他计算模型。例如，人们也可以在非确定性图灵机上讨论语言的可判定性。因此为了避免歧义，通常使用的“递归语言”也可被称作图灵可判定语言，而不是简单的可判定的。
所有递归语言的类通常被称为R，但是这个名称也用于RP类。
这种语言类型在乔姆斯基层级（）中没有定义。所有递归语言也都是递归可枚举的。所有正则语言，上下文无关语言的和上下文有关语言都是递归的。
递归语言有两个等价的主要定义:
根据第二个定义，任何判定问题都可以用一个对于所有输入，都会最终进入停止状态的算法来证明它是否可判定。一个不可判定问题是一个不可判定的问题。
如上所述，每种上下文有关语言都是递归的。因此，递归语言的一个简单例子是集合 L={abc， aabbcc, aaabbbccc,...}；更正式的表达方式是，集合
是上下文有关的，因此它是递归的。
关于非上下文有关的可判定语言的例子，则更难描述一些。这里有一个需要熟悉数理逻辑知识的例子：Persburger算法是带有加法(但没有乘法)的自然数的一阶理论。当Persburger算法中的这套合式公式上下文无关时，对于某个常数c> 0（），每台接受Persburger算法中真命题集的确定性图灵机，都有一个最小为 的最差运行时间。这里的n表示给定公式的长度。因为每种上下文有关语言都可以被一个线性有界自动机接受，并且确定性图灵机能够模拟这种自动机，然而这种图灵机在给定某个常数c的情况下，却具有最大为 的最差运行时间，所以Presburger算法中的这组有效公式并非为上下文有关的。从正面来说，我们知道存在一种确定性图灵机，运行时间为最多n的三次方，这里n可以决定Persburger算法（）中的这组永真公式。所以说，这个例子就是关于一种可判定但却非上下文有关语言的。
递归语言是在下列运算中是闭合的。也就是说，如果L和P是两个递归语言，那么下列语言也是递归的:
注意最后一条属性，差集可以用交集和补集来表示。
暂无