递归

有关计算机科学中的递归，请参阅递归函数．

递归正式确定认识到较小情况的解决方案如何，通过图层层层，建立在任何问题的情况下，无论多么巨大。毋庸置疑，弄清楚如何同时解决无数问题。这就是这个Wiki页面将解释的内容，因此在解决某些问题的情况下，这种解决方法有时感觉有点循环和奇怪的循环。

一些迹象递归可能是攻击问题的好方法如下：

1. 问题要求大写的值，您可以确定小值或者它们。
2. 小病例和大病例之间有明显的联系。

此示例问题可以直接解决，无需递归。但递归解决方案是一种美观而有效的方法。

下一个将需要多少个红色三角形瓷砖 $（$这 $4 ^ \文本{th})$这一星级模式？

通过计数来解决这个难题并没有羞耻（虽然这样做可能比你想象的更棘手）。您甚至可能会以聪明的方式提出聪明的方式 - 例如，通过认识到明星的每个臂需要相同数量的三角形。但这些方法都不是实用的或与递归一样优雅。

如果你还不相信递归方法值得投资，可以考虑计算 $1000 ^ \ text {th}$这个模式的级别。共有23988件。

为什么使用递归?因为没人想数那么多!使用递归，在下一节结束时您将能够轻松地解决这个问题。

递归应该作为一种技术应用，当您解决的问题就像洋葱一样。使用递归需要实现一个可能会让你哭泣的大，复杂的问题真的只是一个稍微较小的问题，以及一个超薄层。并且那个问题，又是一个略小的问题，加上一个超薄层......

递归解决问题的步骤

1. 创建和分析问题的小案例。

2. 尝试使用较小的案例构建更大的案例。

3. 对小案件与大案件之间的关系做一个猜想。

4. 证明您的猜想并将其转换为一个通用的公式，该公式将答案较小/更简单的问题的答案找到较大/更困难的案例的答案。

5. 使用第4步的公式来建立你所关心的特定层的溶液。

批判性地，在步骤4中，更小和更大的情况之间的关系需要是一个用于构造的一般性任何从较早的/较小的案例中得出的问题，而不是从较早的具体案例中得出具体的复杂案例。

这些步骤是有效和完美地解决许多问题的秘密，这些问题会让普通人哭泣。

这个星形图案的下一层(第4层)需要多少红色三角形瓷砖?

---

我们将用递归来解决这个问题。递归思维完美而有效地解决了这个问题。

步骤1创建和分析问题的小案例。

这个问题的自然情况是恒星的顺序层:

• 第一层有12个三角形。
• 第二层有36个三角形。
• 第三层有60个三角形。

步骤2尝试使用较小的案例构建更大的案例。

比较 $1 ^ \ text {st}$层到了 $2 ^ \文本{和}$层, $2 ^ \文本{和}$层到了 $3 ^ \ text {rd}$层:

步骤3对小案件与大案件之间的关系做一个猜想。

注意，通过将一层中的几组三角形从中心移开，然后添加24个额外的菱形三角形对，我们可以将每一层的图案做成下一层。

这两个顺序层之间的几何关系是通用的任何两个连续的层。

第四步证明您的猜想并将其转换为一个通用的公式，该公式将答案较小/更简单的问题的答案找到较大/更困难的案例的答案。

每层都需要24日更多的三角形比在它之前的层！

如果 $C_n$case的答案是什么 $N$那么，这个问题 $C_n = c_{n-1} + 24$和 $c₁$= 12由于与一层，星形中有12个三角形。

第5步使用第4步的公式来建立你所关心的特定层的溶液。

求出三角形的个数 $4 ^ \文本{th}$层:

• 案例1：初始明星中有12个三角形。
• 案例2：有 $12 + 24 = 36$三角形在 $2 ^ \文本{和}$层。
• 案例3:有 $36 + 24 = 60$三角形在 $3 ^ \ text {rd}$层。
• 案例4:有 $60 + 24 = {84}$三角形在 $4 ^ \文本{th}$层。 $_ \广场$

太大了，数不过来?确实。递归太大了吗？从来没有!

要找到递归关系，需要在每个问题的情况和之前的情况之间找出一些规则关系。但很多时候，它不会仅仅是在相关的情况下。有时，后来的病例会由两个、三个或任何数量的以前病例合并而成。

你正在为朋友创建一个瓷砖设计目录。在这一系列的设计中，瓷砖的面积是2“x 16”，每块瓷砖都是1“x 2”。用贴图覆盖区域有多少种不同的方法?

几个例子:

步骤1创建和分析问题的小案例。

为了使这个问题更简单，可以减小面积的长度。例如，计算一个2 × 5的矩形有多少种平铺方式是非常简单的。此外，我们在这个阶段的一厢情愿的想法是，如果我们已经知道2“x 16”情况的解，那么2“x 16”情况的解就会很容易算出来……

这个推理建议的问题顺序是考虑平铺一个2 x 1的区域，然后是一个2 x 2的区域，然后是一个2 x 3的区域，等等。因此，一般情况是2“x n”。

解决最小情况

$c_1 = 1$

有一种方法来平铺1 × 2的区域。

---

$c_2 = 2$

有两种方法来平铺一个2 × 2的区域。

---

$C_3 = 3$

有3种方法来平铺一个3 × 2的区域。

---

$C_4 = 5$

有5种方法来平铺一个4 × 2的区域。

步骤2尝试使用较小的案例构建更大的案例。

我们可以一次处理一个案子或者，在任何时候，我们都可以开始寻找规律。尝试使用上面的集合作为工具来识别所有的平铺模式 $C_5$．你怎么能从较小的瓷砖模式中进行更大的瓷砖模式？

步骤3对小案件与大案件之间的关系做一个猜想。

举个例子，我们试着计算出瓷砖图案的数量 $n = 5.$，也就是用多米诺骨牌平铺5 × 2区域的方法的数量。首先，我们知道至少有5种方法可以做到这一点:每一种都采取 $n = 4.$解决方案并在左侧添加一个新的垂直图块：

但有更多的解决方案吗？是的。上面是所有以一个垂直瓦片开头的解决方案，但是所有的解决方案都达到了左边两个水平瓦片的所有解决方案？

如果在左边的两个瓷砖之后还有3英寸的空间要填满，有多少种方法可以填满这3英寸? $c_3 = 3。$

第四步证明您的猜想并将其转换为一个通用的公式，该公式将答案较小/更简单的问题的答案找到较大/更困难的案例的答案。

推广这个观察，对于任何 $N$''x 2'区域，有 $C_ {n}$左侧有一个垂直多米诺骨牌的倾斜，和 $C_ {2}$最左边有两个水平的多米诺骨牌。所以 $C_n = C_{n-1} + C_{n-2}$．的话说,每一种情况的解都是前两种情况解的和。

这是斐波纳契序列！除了基本情况项，在这种情况下， $c_1 = 1$和 $c_2 = 2$．

第5步使用第4步的公式来建立你所关心的特定层的溶液。

此时，在递归过程中的任何特定点停止可能感觉有点随意——为什么要在 $1001 ^ \ text {st}$建筑物的地板，当你可以将电梯拿到月球......和超越？

每当你定义递归过程时，你都可以想象采取这个过程的无限限制，询问，“我们在一遍又一遍地重复过程时，我们接近了什么？”有时候，无限令人惊讶地递归。

分形都是递归关系无限扩展的美丽应用。一种特殊的分形叫做迭代函数系统几乎只是对无限踢的视觉递归。这些分形使用递归过程进行。以下是ifs fractals的一些例子：

Sierpinski的三角形

1)从边长为1的直角等腰三角形开始。

2)画线连接每条边的中心，去掉这些边形成的倒三角。

3)画线连接其余实心三角形的每条边的中心。去掉这些边形成的倒三角形。

．．．一遍又一遍重复步骤3的过程，每次从每个剩余三角形的中心移走较小的、倒三角形。

重复执行步骤3无限很多次…

无穷多。例如，想象一个图形原点处的三角形的左角和三角形的左边缘是一条从0到1的垂直线。在过程的第一次迭代中，中心点 $\ frac12$然后删除，然后 $\ frac14$和 $\ frac34,$然后 $Frac18，\ frac38，\ frac58，$和 $\ frac78,……$等。但 $\ frac13$永远不会被删除，也不会 $\ frac19 \ frac1{27},……$事实上，在图的垂直边缘上，即使无限多点被移除，更多的积分留在分形。

图像中不会留下线段。最终分形的垂直左边缘看起来像一条线，但是已经从中删除了许多点，没有剩下的连续部分。换句话说，最终，图像中的每个线段都有至少一个点从中移除，打破它。因此，每个部分的最终“长度”将为0。

一个也没有。对于任何一个初始存在的实体区域，最终，它的一部分会被递归过程删除。因此，在无限次执行递归过程后，不会留下任何坚实的区域补丁。

结论:分形是奇怪的！

• 线性递归关系
• 用代换法求不规则闭型解
  (将递归模式转换成一个公式，可以立即给出任何特定情况的答案，而不需要依次计算出每个较小的解决方案。)
• 通过主定理找到封闭的复发关系形式
• 甚至更多关于复发关系
• 产生功能 - 解决复发关系
• Y-Combinator（Lambda Calculus）

主要文章：组合学中的未解问题

• 待办事项:例1
• 待办事项:例2