第四章 - 归纳与递归

约 916 个字 预计阅读时间 3 分钟

数学归纳法

一般而言，数学归纳法 (mathematical induction) 可用于证明这样一类命题：对于所有正整数 \(n\)，命题函数 \(P(n)\) 为真。数学归纳法的证明包含两个步骤：

• 基础步骤：证明命题 \(P(1)\) 为真。
• 归纳步骤：证明对每个正整数 \(k\)，蕴含式 \(P(k) \to P(k + 1)\) 为真。

形式化地表示为 \((P(1) \wedge \forall k (P(k) \to P(k + 1))) \to \forall n P(n)\)。

相信读者通过之前的数学学习，对数学归纳法应当是非常熟悉的，因此我们还是来关注一些有趣的内容。首先笔者希望展示课本中这样一段内容：

这段内容非常精辟地指出了数学归纳法的优势和局限，笔者强烈建议每个有意愿进行数学研究的读者理解这段内容，以对数学归纳法的应用产生更加深刻的理解。

强归纳法与良序性

强归纳法

强归纳法 (strong induction) 是数学归纳法的一种变体，也称作完全归纳法 (complete induction) 或数学归纳法第二原理。其证明包含两个步骤：

• 基础步骤：证明命题 \(P(1)\) 为真。
• 归纳步骤：证明对每个正整数 \(k\)，蕴含式 \([P(1) \wedge P(2) \wedge \cdots P(k)] \to P(k + 1)\) 为真。

良序性

数学归纳法和强归纳法的有效性都源于整数集合的基本公理，即良序性公理 (well-ordering axiom)。良序性公理断言：任意一个非空的非负整数集合都有最小元素。

递归与结构归纳法

递归

递归 (recursive) 是指用对象定义自身的过程，其常被应用到各种定义之中。

为了定义以非负整数集合作为其定义域的函数，可以按照如下两个步骤进行递归：

• 基础步骤：定义这个函数在 \(0\) 处的值。
• 递归步骤：给出从较小的整数处的值来求出当前的的值的规则。

这样的定义称作递归定义或归纳定义，递归定义的函数都是良定义的 (well-defined)，即对于每一个正整数，函数对应取值是清楚定义的。

除了函数外，递归还可以广泛地应用于定义各种结构。

举例来说，字母表 \(\sum\) 上的字符串的集合 \(\sum^{*}\) 递归地定义为：

• 基础步骤：\(\lambda \in \sum^{*}\)，\(\lambda\) 是不含任何符号的空串。
• 递归步骤：若 \(w \in \sum^{*}\) 且 \(x \in \sum\)，则 \(wx \in \sum^{*}\)。

类似地，归纳定义还可以用于定义树、图等结构。

结构归纳法

结构归纳法 (structural induction) 是不止可用于正整数，而可用于所有递归结构的，更加一般化的归纳法。其证明包含两个部分：

• 基础步骤：证明对于递归定义的基础步骤中，所规定的属于该集合的所有元素，结果成立。
• 递归步骤：证明若对于递归定义的递归步骤中，用来构造新元素的每个元素来说命题为真，则对于这些新元素来说结果成立。

递归算法

递归更广泛的应用在于各式递归算法。一般地，递归算法的正确性需要通过强归纳法（而非数学归纳法）证明。

连续应用递归定义，以求得或接近目标值的过程称作迭代 (iteration)。迭代算法往往具有清晰的实现和较少的计算量，因此也有广泛的应用。