在数学、逻辑和计算机科学中，递归语言或遞迴語言是也叫做可判定语言或图灵可判定语言的形式语言类型。所有递归语言的类经常被称为 R。这种语言类型在乔姆斯基层级中没有定义。 递归语言有两种等价的主要定义: 递归语言是在形式语言的字母表上的所有可能的字的集合的递归子集。 设 S ⊆ Σ* 是一个语言，M 是一台图灵机，...

} 换句话说，集合 S 是递归的，当且仅当指示函数 1 S {\displaystyle 1_{S}} 是可计算的。 空集 自然数 自然数的所有有限子集（有限子集并非可数子集，后者可能有无限多的元素） 素数的集合 递归语言是在形式语言字母表之上所有可能词的集合中的递归集合。 如果 A {\displaystyle...

在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0语言。所有递归可枚举语言的类叫做RE。 递归可枚举语言定义：设S ⊆ Σ*为一个语言，E是一个枚举器，若L（E） = S，则称E 枚举了语言S。若存在这样 的E，S就称为递归可枚举语言。...

互递归是数学与计算机科学中一种递归，指两个数学或计算机对象如函数或数据类型互相定义。互递归在函數程式語言或某些问题域中非常常见，如递归下降分析器（英语：recursive descent parser），其中数据类型是自然地互相递归定义的。 采取互递归定义的最重要的基本数据类型是树。这可以用于定义森林（树的列表）:...

递归可以有下列解释： 递归 - 一种函数的定义中使用函数自身的方法 递归语言 - 在数学、逻辑和计算机科学中的一种可判定语言 递归集合 - 一种可判定集合 递归缩写 - 一种在全称中引用它自己的缩写方式 递归 (计算机科学) 递归可枚举集合 递归可枚举语言 原始递归函数...

在计算机编程语言中，递归类型（又名：递归定義、隱含類型或隱含定義）是一种特殊的数据类型，它表示自身内部可能包含其它的同样类型的值。 以下是一個在Haskell中使用链表类型的一个列子： data List a = Nil | Cons a (List a) 这表示a的链表s可以是一个空表或一个con...

所有递归集合都是递归可枚举的，但不是所有递归可枚举集合都是递归的。 递归可枚举语言是在形式语言的字母表上所有可能词的集合中的递归可枚举集合。 Matiyasevich 定理声称所有的递归可枚举集合都是丢番图集合。 简单集合是递归可枚举的但不是递归的。 创造集合是递归可枚举的但不是递归的。 生产集合不是递归可枚举的。 对于偏可计算函数 ϕ...

遞迴式方法可以被用於解決很多的電腦科學問題，因此它是電腦科學中十分重要的一個概念。 絕大多數程式語言支援函式的自呼叫，在這些語言中函式可以通過呼叫自身來進行遞迴。計算理論可以證明遞迴的作用可以完全取代迴圈，因此有很多在函數程式語言（如Scheme）中用递归来取代循环的例子。 電腦科學家尼克勞斯·維爾特如此描述遞迴：...

等语言来说，在函数最后 return g(x); 并不一定是尾递归——在返回之前很可能涉及到对象的析构函数，使得 g(x) 不是最后执行的那个。这可以通过返回值优化来解决。 若函数在尾位置调用自身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归。尾递归也是递归的一种特殊情形。尾递归...

theory）有所重叠。 数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相当大的知识和方法上的重叠，而没有明显的界限。 递归论所考虑的基本问题是，给定一个从自然数到自然数的函数f，...

递归（英語：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。 在数学和计算机科学中，递归...