计算机科学基础/递归再探

递归再探

递归解法提供了另一种强大的方法来解决自相似问题。我们将要研究的例子是二分查找解法。

二分查找如何工作？

在排序列表中识别目标项目的过程。首先是基本情况，直接判断中间项目是否等于目标。如果中间项目等于目标，则搜索完成，并报告索引。如果列表为空，则搜索报告 -1 或未找到。否则，判断目标是大于还是小于中间项目，以决定搜索列表的哪一半。

接下来，如果中间项目大于目标，则搜索列表的前一半，否则，我们搜索列表的后一半。这与我们最初开始时遇到的问题相同，使其成为一个递归或自相似问题。

下图是二分查找代码实现。基本情况和递归情况已标出。

二分查找用于在排序列表中查找项目（目标）。它由组成递归解法的基本情况和递归情况组成。

二分查找：抽象简化

简化二分查找解法的一个好方法是使用抽象。之前显示的图像使用了一个名为“中间位置”的辅助块，该块用于在给定排序列表的第一个和最后一个索引时找到中间索引（见下文）。

二分查找中用于在给定输入的第一个和最后一个索引之间找到中间索引的辅助块。

简化二分查找解法的另一种方法是增加另一个抽象层。下面的辅助块显示了目标和列表作为输入传递到“二分查找”块中（见下文）。当递归搜索块检测到排序列表的第一个和最后一个索引时，实际的递归解法得以实现。“二分查找”块允许用户调用递归搜索，而无需用户提供第一个和最后一个索引。用户只看到开始二分查找所需的信息和/或块。用户将不会看到递归搜索或解决方案背后的幕后过程。

二分查找辅助块，增加了另一个抽象层，通过调用递归搜索块来搜索列表中的目标。

二分查找：跟踪

我们之前讨论过使用“二分查找”简化递归搜索的界面，它将目标和列表作为输入（见下例）。然后，调用“递归查找”，并且立即解决第一个基本情况，因为我们的目标 9 不等于 5。由于目标 9 大于 5（中间索引处的元素），我们搜索列表的后一半（索引 4 到索引 5）。重复该过程，并拆分列表，检查位置和/或索引 4 处的第一个元素。目标大于 7，再次重复递归搜索，再次搜索列表的后一半。基本情况 2 立即解决，目标 9 等于列表中的 9；它位于中间索引 5 处。

现在，由于在索引 5 处找到了目标，递归搜索报告回第二个递归搜索，而第二个递归搜索又报告回第一个递归搜索。最后，索引 5 被报告回“二分查找”块的顶层用户。

此图像显示了当目标等于 9 时如何跟踪二分查找。逐步使用基本情况和递归情况进行报告。

如果在列表中没有找到目标，则二分查找报告 -1（见下文）。会进行相同的递归搜索调用，但在最后一次调用时，开始索引大于结束索引，这表明没有找到目标，并且已到达列表的末尾。

此图像显示了当目标在排序列表中找不到时如何跟踪二分查找。如果列表中没有目标，则解决方案报告 -1 或未找到。

科赫曲线

1904 年，Helge von Koch 发现了冯·科赫雪花曲线，“一条在分形几何学研究中很重要的连续曲线”（3）。科赫曲线从一条长度为 1 个单位的单线段开始。然后，用四个新的线段替换该线段，每个线段的长度是原始线段的三分之一，也称为生成器。该过程无限重复，并生成科赫曲线。下图显示了阶段 0 到 2 的过程。

这显示了生成器（阶段 0）和科赫曲线的阶段 1 和 2 的迭代。

科赫曲线的长度是无限的。该曲线是递归的另一个有趣的实现，它是自相似的；曲线不断复制自身。

科赫雪花

在等边三角形的三个边上使用相同的科赫曲线生成器，我们可以看到重复的迭代最终开始看起来像雪花（请参阅 科赫雪花）。雪花具有无限的周长和有限的面积。

检查科赫雪花的每个阶段，都会创建一个关于每边线段数量、长度和曲线总长度的模式，如下所示。每边线段的数量是上一个阶段的四倍。每次将线段长度分成相等的三个部分，这将给出每个线段的长度。原始阶段，等边三角形，是为什么我们取每边线段数量的三倍除以线段长度的 stage 幂次（当前正在实现的阶段）。

通过跟踪不同的迭代，可以看出科赫雪花的模式。

探索问题

研究科赫曲线和雪花图案已经确立，并显示了如何重复相同的过程来生成每个阶段。我们可以使用递归过程来解决相同问题的抽象。

• 第 N 次迭代的总长度是多少？查看数字在简化之前和之后形成的模式。
• 您期望科赫曲线是什么样子的？换句话说，您期望无限次重复此操作会发生什么？
• 科赫曲线的长度是多少？
• 你能估计每个阶段的面积吗？最终雪花的面积是多少？

回顾之前的题目，我们可以开始观察科赫曲线和科赫雪花的行为。

1. 根据已建立的模式，很明显第 N 次迭代的总长度将是 3*(4/3)ⁿ。
2. 由于科赫曲线无限重复，它会开始看起来更平滑，因为线条会看起来越来越近，尽管永远不会接触。
3. 科赫曲线的长度是无限的（在将生成器应用无限次之后）。
4. 最终雪花的面积是有界的（有限的）。