5.3 递归定义和结构递归法

递归定义 / 归纳定义 【函数】：

定义一个以自然数集为定义域的函数 \(f\)，分为两步：

1. 基础步骤：给出 \(f\) 在 \(0\) 处的值 \(f(0)\)。

2. 递归步骤：给出从 \(f(n')\)（其中 \(n' < n\)）来定义 \(f(n)\) 值的规则。

递归定义【集合】：

定义一个集合 \(S \subset \mathbb{Z}\)，分为两步：

1. 基础步骤：指定一个初始的元素集合。

2. 递归步骤：给出从集合中已知元素生成新元素的规则。

排除规则：

集合 \(S\) 除基础步骤中指定的元素或通过递归步骤生成的元素外，不包含其他任何元素。

递归定义【结构】：

——扩充二叉树的集合

• 基础步骤：空集是一个扩充二叉树。

• 递归步骤：假设 \(T_1\) 和 \(T_2\) 是两个不相交的扩充二叉树，则从根节点 \(r\)（\(r\) 不在 \(T_1\) 或 \(T_2\) 中）出发，向 \(T_1\)（非空时）的根节点和 \(T_2\)（非空时）的根节点分别添加一条边所形成的图是一个扩充二叉树。

递归定义的集合与结构 结构归纳法 递归算法 证明递归算法的正确性 递归与迭代 归并排序