递归

1. 编程语言中，函数直接或间接调用函数本身的过程。该函数称“递归函数”。作为一种算法在程序设计语言中广泛应用。只需少量的程序就可描述出解题过程所需要的多次重复计算，大大减少程序的代码量。

2. 转换生成语法术语。有三个含义：（1）指语法的一种属性，这种属性使得一组有限的规则可反复使用，从而生成语言的无限句子。如在英语语法的基础部分有以下几条重写规则（S为句子，NP为名词短语，VP为动词短语，V为动词，Det为限定词，括号表示可选可不选）：（a）S→NPVP，（b）VP→VNP，（c）NP→（Det）N（S）……。这几条规则可以说明下面的句子：The man（whokicked the ball）scored the goal（that won the game）[（踢球的）那个人踢进一球（赢了这场比赛）]，这里（S）根据规则（c）两次嵌入NP，S这个符号既可出现在箭头的左边，也可出现在箭头的右边，这个S就是递归的，可称为“递归符号”，或“递归要素”。（b）和（c）规则中右边的S表明可再次运用规则（a），并在（a）之后再运用（b）和（c），然后又可再次运用（a）。这样反复递归地运用这些规则就可产生无限长和无限复杂的基础短语标记。递归是语言创造性的表现。（2）在数学中可计算的函数，大多是由一些基本类型函数组成，这些函数被称作“递归函数”。根据这个概念，生成语法作为一个规则系统，也可被看成是一种递归函数。（3）一个集合，如果能机械地判定任意一个成分是否属于这个集合，此集合即为递归集合，而递归集合都是递归可枚举集合。生成语法输出的集合都是具备语义和音位解释的表层结构，其是否符合语法都可作机械判定，故生成语法输出的句子集合也是递归可枚举集合。