本节对应原书 PDF 第 31–32 页。定义、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

用自身定义自身称作递归定义或归纳定义.

例如，a^n 可以递归定义如下：

a^0 = 1
a^n = a^{n-1} \cdot a, \quad n = 1, 2, \cdots

对任意给定的 k，从 0 开始，依次对 n = 1, 2, \cdots 直到 k，重复计算第二个式子即可得到 a^k. 如求 2^5，计算如下：

\begin{aligned} 2^0 &= 1 \\ 2^1 &= 2^0 \times 2 = 1 \times 2 = 2 \\ 2^2 &= 2^1 \times 2 = 2 \times 2 = 4 \\ 2^3 &= 2^2 \times 2 = 4 \times 2 = 8 \\ 2^4 &= 2^3 \times 2 = 8 \times 2 = 16 \\ 2^5 &= 2^4 \times 2 = 16 \times 2 = 32 \end{aligned}

下面举几个例子.

例 1.22 菲波那契数列 \{f_n\} 递归定义如下：

\begin{aligned} f_0 &= 1 \\ f_1 &= 1 \\ f_n &= f_{n-1} + f_{n-2}, \quad n = 2, 3, \cdots \end{aligned}

不难求得 f_0 = 1，f_1 = 1，f_2 = 2，f_3 = 3，f_4 = 5，f_5 = 8，f_6 = 13，\cdots.

例 1.23 集合 A 的递归定义如下：

（1）3 \in A；

（2）若 x, y \in A，则 x + y \in A；

（3）只有有限次使用（1）和（2）得到的数属于 A.

可以看出 A 是 3 的所以正整数倍组成的集合，即 A = \{3n \mid n \in \mathbf{Z}^+\}.

证明如下. 首先，\forall n \in \mathbf{Z}^+，由（1），3 \in A；用（2），因为 3 \in A，3 \in A，得 3 + 3 = 2 \times 3 \in A；再用（2），6 \in A，3 \in A，得 6 + 3 = 3 \times 3 \in A；如此重复用 n - 1 次（2）得到 3n \in A. 得证 \{3n \mid n \in \mathbf{Z}^+\} \subseteq A.

反之，\forall x \in A，设 x 是使用 k 次（2）得到的，对 k 用第二数学归纳法证明.

归纳基础 k = 0，此时 x = 3. 3 是 3 的正整数倍.

归纳步骤 \forall t \in \mathbf{N}，假设当 0 \leqslant k \leqslant t 时，x 是 3 的正整数倍. 要证当 k = t + 1 时，x 是 3 的正整数倍. 设在最后一次用（2）得到 x 时，x = y + z，其中 y, z \in A. 显然，得到 y 和 z 使用（2）的次数小于等于 t. 根据归纳假设，y 和 z 都是 3 的正整数倍，因而 x 也是 3 的正整数倍. 得证 A \subseteq \{3n \mid n \in \mathbf{Z}^+\}.

例 1.24 算术表达式的归纳定义如下：

（1）任何实数和变量都是算术表达式；

（2）如果 f, g 是算术表达式，则 (f + g)，(f - g)，(f * g) 是算术表达式；

（3）如果 f, g 是算术表达式且 g \neq 0，则 (f / g) 是算术表达式；

（4）如果 f 是算术表达式，则 \forall n \in \mathbf{Z}^+，(f \uparrow n) 是算术表达式；

（5）只有有限次使用（1）～（4）得到的式子是算术表达式.

其中 \uparrow 是幂运算.

例如，((3 * x) - 1)，(((2 * (x \uparrow 2)) + (5 * x)) - 4)，(((x + y) - z)/(5 + x)) 都是算术表达式. 根据运算的优先级别，删去不必要的圆括号（包括最外层的圆括号）就是通常形式的算术表达式.

递归定义是一种重要的定义形式，在后面有多处用到.

解读：递归定义必须恰好包含两部分——"基础情形"直接给出最初的对象（如 a^0 = 1、3 \in A），"归纳条款"由已知对象造出新对象；再加上一条"只有有限次使用前面条款得到的才属于它"，把定义域封死。少了最后这条限制，集合里就会混进本来不该有的元素。