为了定义非负整数集合作为其定义域的函数，使用两个步骤：
基础步骤：规定这个函数在0处的值。递归步骤：给出从较小的整数处的值来求出当前的值得规则。例1 假定f是用f(0)=3,f(n+1)=2f(n)+3来递归定义的。求出f(1)、f(2)、f(3)和f(4)。
解：从这个递归定义得出
$$f(1)=2f(0)+3=2 \cdot 3 + 3 = 9$$$$f(2)=2f(1)+3=2 \cdot 9 + 3 = 21$$$$f(3)=2f(2)+3=2 \cdot 21 + 3 = 45$$$$f(4)=2f(3)+3=2 \cdot 45 + 3 = 93$$递归定义的函数是良定义的。即对于每一个正整数，函数对应取值是清楚定义的。这意味着给定任意整数，我们可以使用定义的这两个部分得到对应整数的函数值，无论怎么使用这两部分定义都会得到同样的值。
正如在函数的递归定义中那样，集合的递归定义有两个部分：基础步骤和递归步骤。在基础步骤中，规定初始的一些元素。在递归步骤中，给出用来从已知属于集合的元素来构造集合的新元素的规则。
例5：考虑如下定义的整数集合的子集S。
基础步骤：$3 \in S$。
递归步骤：若$x \in S$ 且 $y \in S$，则$x+y \in S$。
基础步骤中求出的S中的新元素是3，递归步骤的首次应用求出的是3+3=6，递归步骤的第二次应用求出的是3+6=6+3=9以及6+6=12，等。
定义1：字母表$\sum$上的字符串的集合$\sum^*$递归地定义为：
定义2：通过连接运算可以组合两个字符串。设$\sum$是符号的集合，$\sum^*$是$\sum$中符号形成的字符串的集合。可以如下定义两个字符串的连接，用$\cdot$表示：
递归定义的另一种重要用途是定义各种类型的合式公式。
例8（复合命题的合式公式）：可以定义关于T、F、命题变元以及集合$\{\lnot,\land\lor,\to,\leftrightarrow\}$中运算的复合命题的合式公式的集合。
定义3：以下步骤可以递归地定义根树的集合，其中根树是由一个顶点集合和连接这些顶点的边组成的，顶点集合包含的一个特殊顶点，称为树根。
定义4：以下这些步骤可以递归地定义扩展二叉树的集合：
定义5：以下这些步骤可以递归地定义满二叉树的集合：
结构归纳法证明包含如下两个部分：
可以定义$N \times N$（非负整数的有序对）上的序，规定如果$x_1 < x_2$或者$x_1 =x_2$且$y_1 < y_2$，则$(x_1, x_2)$小于等于$(y_1, y_2)$。这称为字典序。具有这个序的集合$N \times N$具有性质：$N \times N$的每个子集合都有最小元。这意味着可以递归地定义满足$m \in N$和$n \in N$的项$a_{m,n}$，并且用数学归纳法的变种来证明关于这些项的结果。
In [ ]: