这里解释一下为什么一天发的，但是却是一个二十，一个二十一，因为上一篇是我昨天写一半，得睡觉了，所以今天写完才发的。

菜鸟已经感觉手指扛不住了，所以更新完这篇得休息了，读者谅解，话不多说，冲冲冲

数学归纳法

上次我们聊了迭代法及其应用，不过你知道吗，对于某些迭代问题，我们其实可以避免一步步的计算，直接从理论上证明某个结论，节约大量的计算资源和时间，这就是我们今天要说的数学归纳法。

定义

在数论中，数学归纳法是用来证明任意一个给定的情形都是正确的，也就是说，第一个、第二个、第三个，一直到所有情形，概不例外。

数学归纳法的一般步骤是这样的：

证明基本情况（通常是n = 1 的时候）是否成立
假设n = k -1 成立，再证明n = k 也是成立的（k 为任意大于1的自然数）

特点

用迭代法的计算相比，数学归纳法最大的特点就在于 “ 归纳 ” 二字。它已经总结出了规律。只要我们能够证明这个规律是正确的，就没有必要进行逐步的推算，可以节省很多时间和资源。

举例

上节我们提到，在棋盘上放麦粒的规则是，第一格放一粒，第二格放两粒，以此类推，每一小格内都比前一小格多一倍的麦子，直至放满n个格子。这个时候，国王想知道总共需要多少粒麦子。

我们小时候都玩过 “ 找规律 ” ，你看看是不是这样？

根据这个观察，我们是不是可以大胆假设，前n个格子的麦粒总数就是 2ⁿ-1 呢？

对于类似这种无穷数列的问题，我们通常可以采用数学归纳法（Mathematical Induction）来证明。

证明

菜鸟感觉这根本不是重点，直接截图了，复制都懒得搞，其实感觉这一节没什么写的，其实知道数学归纳法是怎么个过程就好，难受，又被马扁子忽悠了一节课！????

递归调用和数学归纳

我们不仅可以使用数学归纳法从理论上指导编程，还可以使用编程来模拟数学归纳法的证明。如果你仔细观察一下数学归纳法的证明过程，会不会觉得和函数的递归调用很像呢？

这里我通过总麦粒数的命题来示范一下。首先，我们要把这个命题的数学归纳证明，转换成一段伪代码，这个过程需要经过这样两步：

你应该看出来了，这两步分别对应了数学归纳法的两种情况。

在数学归纳法的第二种情况下，我们只能假设n = k -1 的时候命题成立。但是，在代码的实现中，我们可以将伪代码的第二步转为函数的递归（嵌套）调用，直到被调用的函数回退到n = 1的情况。然后，被调用的函数逐步返回 k - 1 时命题是否成立。

我们可以看出来，递归调用的代码和数学归纳法的逻辑是一致的。一旦你理解了数学归纳法，就很容易理解递归调用了。只要数学归纳证明的逻辑是对的，递归调用的逻辑就是对的，我们没有必要纠结递归函数是如何嵌套调用和返回的。

不过，和数学归纳证明稍有不同的是，递归编程的代码需要返回若干的变量，来传递 k - 1的状态到 k 。

这是求米粒数的代码结构图：

从这个图可以看出，函数从 k = 63 开始调用，然后调用 k - 1 ，也就是 62 ，一直到 k = 1 的时候，嵌套调用结束，k - 1 的函数体开始返回值给 k - 2 的函数体，一直到 k = 63 的函数体。从 k = 63,62,…1 的嵌套调用过程，其实就是体现了数学归纳法的核心思想，我把它称为逆向递推。而从 k = 1,2,…63 的值返回过程，和上一篇中基于循环的迭代是一致的，我把它称为正向递推。

小结

上一节我讲了迭代法是如何通过重复的步骤进行计算或者查询。与此不同的是，数学归纳法在理论上证明了命题是否成立，而无需迭代那样反复计算，因此可以帮助我们节约大量的资源，并大幅地提升系统的性能。

数学归纳法实现的运行时间几乎为 0 。不过，数学归纳法需要我们能做出合理的命题假设，然后才能进行证明。虽然很多时候要做这点比较难，确实也没什么捷径。你就是要多做题，多去看别人是怎么解题的，自己去积累经验。（极客时间甩锅是真的强，这让你感觉学不好完全是因为自己，极客时间的垃圾不负责任，????）

递归的函数值返回实现了从 k = 1 开始到 k = n 的迭代。