在數學、邏輯學和計算機科學中，如果一種形式語言（取自固定字母表的符號有限序列的集合）是該語言字母表上所有可能的有限序列集合的遞歸子集，則稱為遞歸。等價地，如果存在一個全圖靈機（對每一個給定的輸入都會停止的圖靈機），當給定一個有限的符號序列作為輸入時，如果它屬于該語言，就接受它，否則就拒絕它，那么這種形式語言就是遞歸的。遞歸語言也被稱為可解碼語言。可判定性的概念可以擴展到其他計算模型。例如，我們可以談論在非決定性圖靈機上可解碼的語言。因此，只要有可能出現歧義，遞歸語言的同義詞就是圖靈可判定語言，而不是簡單的可判定。所有遞歸語言的類別通常被稱為R，盡管這個名字也被用于RP類。這種類型的語言在(Chomsky1959)的Chomsky等級體系中沒有定義。所有的遞歸語言也是可遞歸列舉的。所有正規的、無語境的和語境敏感的語言都是遞歸的。

對于遞歸語言的概念，有兩個相當的主要定義。遞歸形式語言是該語言字母表上所有可能的詞語集合中的一個遞歸子集。遞歸語言是一種形式語言，對于這種語言，存在一臺圖靈機，當遇到任何有限的輸入字符串時，如果該字符串在該語言中，則停止并接受，否則停止并拒絕。圖靈機總是停止：它被稱為決定者，并被稱為決定遞歸語言。根據第二個定義，任何決定問題都可以通過展示其在所有輸入上終止的算法而被證明是可決定的。不可決斷的問題是一個不可決斷的問題。

如上所述，每個上下文敏感的語言都是遞歸的。因此，遞歸語言的一個簡單例子是集合L={abc,aabbcc,aaabbbccc,...}；更正式地說，集合{displaystyleL={{a,b,c}{*}midw=a{n}b{n}c{n}{mbox{forsome}ngeq1,}}。是對環境敏感的，因此是遞歸的。不具有上下文敏感性的可解碼語言的例子更難描述。對于這樣一個例子，需要對數理邏輯有一定的熟悉。Presburger算術是自然數的一階理論，有加法（但沒有乘法）。雖然普斯伯格算術中形式良好的公式集是無語境的，但每個接受普斯伯格算術中真實語句集的確定性圖靈機的最壞情況下運行時間至少為{displaystyle2{2{cn}}}，對于某個常數c>0，最壞情況下的運行時間為，對于一些常數c>0（Fischer&Rabin1974）。

這里，n表示給定公式的長度。由于每一種上下文敏感語言都可以被線性有界自動機所接受，而且這樣的自動機可以被確定性的圖靈機所模擬，其最壞情況下的運行時間最多為{displaystylec{n}}對于某個常數c對于某個常數c，普氏算術中的有效公式集不是對環境敏感的。從正面看，已知有一臺確定性的圖靈機，其運行時間最多為n的三倍指數，可以決定普雷斯堡爾算術中的真實公式集（Oppen1978）。因此，這是一個可解的語言的例子，但不是上下文敏感的。

遞歸語言在以下操作下是封閉的。也就是說，如果L和P是兩個遞歸語言，那么下面的語言也是遞歸的。克萊因星L最后一個屬性來自于集差可以用交集和補集來表示的事實。