递归定义

定义

递归定义(Recursive Definition)是一种定义集合的方法，一般包含三个步骤:
1. 指出有一些基本的元素是在集合中的
2. 给出在集合中已有的元素上构造新元素的方法
3. 指明除了可以由第2条所构造的元素外，没有其余任何元素位于该集合中
注意这里只说了分为三个步骤，不代表每个步骤都只包含一条规则

EXAMPLE:
定义一个偶数集合
正常的定义方法为 $EVEN=\lbrace \text{all positive integers divisible by 2}\rbrace$
也可以使用类似 $EVEN=\lbrace 2n\ for\ n=1,2,3,4,...\rbrace$
使用递归定义:
1. $2$ 在集合 $EVEN$ 中
2. 如果 $x$ 在 $EVEN$ 中，那么 $x+2$ 也在 $EVEN$ 中
3. $EVEN$ 中只包含能从1和2中推导得到的元素
(注：第三条其实是完全多余的，只是写出来更加规范)
或者
1. $2$ 在集合 $EVEN$ 中
2. 如果 $x$ 和 $y$ 都在 $EVEN$ 中，那么 $x+y$ 也在 $EVEN$ 中

当选择一个集合的定义方法的时候，应当顾及到两方面：
1. 这些定义是否易于理解
2. 我们希望通过这个集合证明什么定理
比如在上述例子中，我们想要证明如果 $x$ 和 $y$ 是偶数，那么 $x+y$ 也是偶数的话，直接走第二条就可以得到结论了，但是如果按照传统的偶数定义方式，相比之下就要更加复杂。
这种定义方式之所以被称为是"递归的"，是因为其中一条用于定义集合的规则涉及到集合本身，比如我们使用已有的 $EVEN$ 中的元素来定义新的元素，就像在计算机语言中，可以调用自身的例程也被称为是递归的，他们都引用了自身，是自我指涉的(self-referential)

EXAMPLE
Kleene闭包也可以通过递归定义
1. 对于语言 $\mathcal{S}$ ， $S$ 的所有单词都属于 $\mathcal{S}^\ast$
2. $\varLambda$ 也在 $\mathcal{S}^\ast$ 里
3. 如果 $x$ 和 $y$ 在 $\mathcal{S}^\ast$ 里，那么他们的拼接 $xy$ 也在 $\mathcal{S}^\ast$ 里