螺旋，雪花和树木：图片中的递归

递归是一个强大而精妙的概念。直观了解其结构的一种好方法是使用图形可视化不同的递归模式。在本章中，我们将使用简化的矢量图形库接口Rasterific来生成递归图像。

先前的示例已经使用Point类型将二维平面中的点表示为一对浮点值，表示该点的x和y坐标：

最重要的是，我们使用了两个新定义，即“线”和“路径”，它们将一条线表示为一对起点和终点，并将一条路径表示为任意多个点的列表：

此外，一种颜色由四个值组成，这些值指定该颜色的红色，绿色，蓝色和alpha（不透明度）成分-也称为RGBA颜色表示。各个分量的值应介于0到255之间。较大的值和较小的值将以256为模进行解释。

-红色，绿色，蓝色和不透明度分量的四倍。 -这些值都应在0到255之间。类型Color =（Int，Int，Int，Int）

为了简化颜色的使用，我们为一些基本颜色预定义了常量值。 （我们可以通过列出所有值或函数名称（用逗号分隔，然后只写一次）来将使用同一类型的多个类型签名组合为一个。）

函数drawPicture应用于Picture值，将其绘制在大小为800x800的黑色画布上，其原点（0，0）位于最左侧，最上角，而（800，800）位于最右侧，最下角。

house :: Pathhouse = [（300，750），（300，450），（270，450），（500，200），（730，450），（700，450），（700，750）]门：路径门= [（420，750），（420，550），（580，550），（580，750）]

在以下截屏视频中，我们逐步在操场上建造房屋并尝试使用几种不同的颜色。

但是，通过显式枚举所有坐标来创建图片非常繁琐-相反，我们想编写为我们完成工作的函数。

下面的螺旋图看起来比上面的螺旋图复杂，但实际上花费的精力更少！一旦更仔细地观察图片，其原因就很清楚了：它由一组线组成，所有线都起源于同一点。它们的长度，方向和颜色不同，外线越来越不透明，但是这些变化显然遵循简单的模式。这是个好消息，因为这意味着一旦我们确定了模式，我们就可以编写一个程序，将一行作为参数并创建图片。

一个函数-称为SpiralRays-绘制此螺旋模式需要能够重复执行三个操作，我们可以将每个操作实现为单独的功能：

rotationLine :: Float-＆gt;行-＆gt;线：将线的起点旋转给定角度。

spiralRays函数的调用者应该能够指定图片中的行数，初始行和初始颜色（我们可以将其概括化为也接受旋转角度和比例因子作为参数，但是让我们现在保持简单）。函数SpiralRays本身是遵循我们在递归中讨论的列表生成器模式的递归函数：如果使用第一个参数0调用spiralRays，则它将返回一个空列表。以大于0的第一个参数调用时，它将当前行作为结果列表的第一个元素返回，并作为尾部返回n-1上递归调用的结果（带有褪色，旋转和缩放的行）：

spiralRays :: Int-＆gt;颜色-＆gt;行-＆gt; PicturespiralRays n色线@（p1，p2）| n＆lt; = 0 = [] |否则=（color，[p1，p2]）：螺旋线（n-1）newColour newLine，其中newColour =褪色colorNewLine = scaleLine 1.02（rotateLine（pi / 40）线）

spiralRays的第三个参数模式使用@模式（发音为“ at模式”）。在这里，我们使用行@（p1，p2），它立即将变量line绑定到第三个参数，并将两个变量p1和p2绑定到代表该行的对的第一和第二部分。这很方便，因为我们要整体参考这条线（在newLine计算中作为线），但在为第一个图片[p1，p2]构建长度为2的路径时也要参考其组件p1和p2。

现在，我们讨论了整体递归结构，让我们依次看一下三个函数rotateLine，scaleLine和fade。

回转。去除我们的学校几何知识（或进行快速网络搜索）会告诉我们，将线（（0，0），（x，y））绕原点旋转给定角度alpha会导致线（0，0） ，（x＆＃39 ;, y＆＃39;）），其中

x＆＃39; = x * cos alpha-y * sin alphay＆＃39; = x * sin alpha + y * cos alpha

rotationLine :: Float-＆gt;行-＆gt; LinerotateLine alpha（（0，0），（x，y））=（（0，0，（x＆＃39 ;, y＆＃39;）））其中x＆＃39; = x * cos alpha-y * sin alpha y＆＃39; = x * sin alpha + y * cos alpha

不过，总的来说，我们希望旋转不以原点（0，0）开始的线。不过，我们要绕线的第一个点（即它的起点）进行旋转。为此，我们首先将线移动到原点（减去起点的x1-和y1-值），然后使用上述计算旋转结果线，最后将旋转的线移回其原始起点。总的来说，我们得到

rotationLine :: Float-＆gt;行-＆gt; LinerotateLine alpha（（（x1，y1），（x2，y2））=（（（x1，y1），（x＆＃39; + x1，y＆＃39; + y1）））其中x0 = x2-x1 y0 = y2-y1 x＆＃39; = x0 * cos alpha-y0 * sin alpha y＆＃39; = x0 * sin alpha + y0 * cos alpha

缩放。要按给定因子缩放一条线，我们还需要将其移位以从原点（0，0）开始，然后将移位后的直线的端点的x2-和y2-值与缩放因子相乘，最后将线回到其实际起点：

scaleLine ::浮动-＆gt;行-＆gt;线比例线因数（（x1，y1），（x2，y2））=（（x1，y1），（x＆＃39; + x1，y＆＃39; + y1））其中x0 = x2-x1 y0 = y2-y1 x＆＃39; =因子* x0 y＆＃39; =系数* y0

淡入淡出::颜色-＆gt;褪色（redC，greenC，blueC，opacityC）=（redC，greenC，blueC，opacityC-1）

概括。为简单起见，我们的实现从恒定的角度和比例因子开始。现在让我们对此进行概括。我们可以通过两种方式解决这个问题。首先，我们可以将两个其他参数传递给递归调用：

spiralRays ::浮动->浮动->整数->颜色-＆gt;行-＆gt; PicturespiralRays角度比例因子n色线@（p1，p2）| n＆lt; = 0 = [] |否则=（color，[p1，p2]）：螺旋射线角度scaleFactor（n-1）newColour newLine，其中newColour =淡入淡出的颜色newLine = scaleLine scaleFactor（rotateLine角度线）

但是，由于这两个参数在递归过程中保持不变，因此，另一个更优雅的选择是定义一个执行递归的局部函数，该函数不会显式地将angle和scale因子作为参数传递：

spiralRays ::浮动->浮动->整数->颜色-＆gt;行-＆gt; PicturespiralRays角度比例因子n色线= spiralRays＆＃39; n色线，其中SpiralRays n色线@（p1，p2）| n＆lt; = 0 = [] |否则=（颜色[p1，p2]）：spiralRays＆＃39; （n-1）newColour newLine，其中newColour =淡入淡出颜色newLine = scaleLine scaleFactor（rotateLine角度线）

通过更改颜色，角度和缩放比例，我们可以使用这一递归函数生成许多不同的图片。

以下截屏视频说明了螺旋射线的用法，并将使您对可能的变化有所了解。

本节开始处的橙色螺旋是通过仅在每三个递归步骤上调用newColour计算中的衰落函数来修改newColour的计算而生成的，其中mod使用整数计算除数的余数，即，我们使用了

到目前为止，所有图像都使用pi的整数分数作为旋转角度。通过使用其他分数，我们可以实现各种不同的效果：

您可以通过使用其他颜色处理操作替换淡入淡出功能来添加更多有趣的颜色效果，例如，逐渐在色谱中循环的操作。或者，您可以缓慢地增大或减小旋转角度-即使使用此简单功能，我们也可以产生大量有趣的效果。以下截屏视频通过修改淡入淡出演示了一些颜色效果。

如果我们更改了spiralRay函数，以使不是所有线都具有相同的起点，而是每条线的起点都是前一条线的终点，那么我们将获得一条螺旋形路径。为此，我们需要另一个帮助器函数connectLine。它需要两条线，并将第二条线的起点移动到第一条线的终点，而无需更改该线的长度或方向：

这里我们使用了一些新的Haskell语法：第一行的模式中的下划线（_）是所谓的匿名变量：由于我们不使用该行的该部分，因此我们不需要为此起一个名字；相反，我们可以称它为_。我们可以在同一模式下重复使用匿名变量。除了方便之外，这种表示法还提高了代码的可读性，因为匿名变量向读者发送信号，表明函数的结果不依赖于输入的那部分。

函数connectLine将实际工作推迟到startLineFrom（在这里我们再次使用@ -pattern）：

startLineFrom ::点->行-＆gt; LinestartLineFrom startPoint @（x0，y0）（（xS，yS），（xE，yE））=（startPoint，（（（x0 + xE-xS，y0 + yE-yS））））

现在我们已经准备就绪，可以实现新的螺旋功能。现在，它仅返回单个路径，而不返回图片，因此与颜色选择无关：

螺旋::浮动->浮动->整数->行-＆gt;螺旋路径角度比例因子n线=螺旋线螺旋线所在的n条线n行@（p1，p2）| n＆lt; = 0 = [] |否则= p1：螺旋形（n-1）newLine，其中newLine = connectLine线（scaleLine scaleFactor（rotateLine角线））

与SpiralRays一样，此函数会为pi的整数分数的角度生成规则的螺旋形。

对于比例因子为1（即线长均相同）且角度为pi的整数分数的小数点，生成的路径只是一个多边形，因此我们可以根据螺旋定义多边形函数：

多边形:: Int-＆gt;行-＆gt;路径多边形n线| n＆gt; 2 =螺旋旋转角度1（n + 1）行，其中rotationAngle =（2 * pi）/（fromIntegral n）

为了生成更多不同的螺旋，我们可以将螺旋泛化为每个递归步骤中的角度改变一个给定的因子（而不是使用恒定的角度），或者我们可以生成多种颜色的螺旋。不过，后一种更改要求我们将每条线作为一条路径与一种颜色配对，而不是将螺旋线作为一条单独的路径返回。以下截屏视频说明了一些可能的变化。

分形是不断重复以相同或相似形式出现的模式。在自然界中可以发现类似分形的图案，例如花椰菜的小花或蕨类植物的叶子。

Koch雪花（在瑞典数学家Helge von Koch之后）是这种模式的最简单例子之一。通过从等边三角形开始，然后在每次迭代中，在每条线的中间添加前一个三角形大小的三分之一的等边三角形，然后删除新三角形和底边的线，来构造它们。线份额。

第三，第四和第五个递归步骤分别向所有48、4 * 48和4 * 4 * 48行添加了三角形凸点-如以下三个图像所示。

由于每个行的大小在每个递归步骤中都减少了三分之一，因此在五个递归步骤之后，我们几乎再也无法分辨出各个行。

从科赫雪花的形状可以明显看出，在每个递归步骤中应用于每一行的操作顺序始终是相同的。因此，让我们仔细看看这些操作。我们从点PS到点PE的一条线开始

我们需要将这条线切成三个相等的部分，以获得要构造的等边三角形的基线。由于我们已经实现了scaleLine函数，因此可以使用它来获得该三角形的第一个基点p1，它是缩放线l1的终点。要获得小三角形的第三个点，我们可以将l1与自身连接起来（或者，可以将原始线缩放三分之二）。

在这里，我们使用@模式以及匿名变量将线绑定到变量l1和l2，同时分别提取两条线的端点p1和p3。

现在，我们要做的就是找到新三角形的缺失点，即三角形的“峰值”。同样，我们可以使用一个已经实现的函数，rotateLine。我们将第二条线l2顺时针旋转一整圈的5/6（相当于5/3π弧度）。

我们感兴趣的旋转线的唯一组成部分是端点p2，它是通过模式匹配提取的。

现在，我们已经获得了用于实施Koch雪花的三个部分之一（每个部分对应于初始等边三角形的一条线）的递归构造的所有要素。

kochLine :: Int-＆gt;点-＆gt;点-＆gt; PathkochLine n pS pE | n＆lt; = 0 = [] |否则= [pS] ++ kochLine（n-1）pS p1 ++ kochLine（n-1）p1 p2 ++ kochLine（n-1）p2 p3 ++ kochLine（n-1）p3 pE ++ [pE]其中l1 @（_，p1）= scaleLine（1/3）（pS，pE）l2 @（_，p3）= connectLine l1 l1（_，p2）= rotateLine（5/3 * pi）$ l2

注意如何在where绑定中调用scaleLine，connectLine和rotateLine函数的结果上使用模式匹配。只要知道模式匹配成功，就可以在模式绑定中使用模式匹配，方法与在函数参数中使用模式完全相同。这三个kochLine的绑定会产生三角形的三个点p1，p2和p3，我们需要将它们强加到作为参数传递给kochLine的起点和终点pS和pE所指定的线上，如三个图所示在上一节中。然后，在从pS到pE的那一行上强加一个三角形凸点得到的所有四条线上，我们递归地使用kochLine。

递归的这种用法很有趣，因为它是我们的第一个函数，它在单个递归步骤中多次递归调用自身。具体来说，kochLine使用双向递归，而我们仅在递归中定义了单个递归函数。

要产生完整的雪花，剩下的就是将三条科赫线组合起来以得到整个科赫雪花。为此，在递归深度和基线给定的情况下，我们回收多边形函数以构造初始等边三角形：

kochFlake :: Int-＆gt;行-＆gt; PathkochFlake n line = kochLine n p1 p2 ++ kochLine n p2 p3 ++ kochLine n p3 p1其中[p1，p2，p3，_] =多边形3线

我们再次在where绑定中使用模式匹配来分解多边形的结果。在测试功能时，请注意递归调用的数量增长非常快：递归深度为n，会导致kochLine的3 * 4 n次调用！

正如在上一节中使用递归生成模糊的雪花状外观图一样，我们现在将生成植物形状，称为勾股毕生的树。

您能猜出用来构造这些树的几何图案吗？如果没有，请考虑构建上面显示的三棵树中的第一棵树的第一步。

该树由相互堆叠的一系列正方形组成。这导致令人惊讶的柔软有机外观结构。红线所形成的三角形定义了毕达哥拉斯的三重正方形：基本正方形的面积是在下一次迭代中添加的两个正方形的面积之和。树木的区别仅在于在每个步骤中使用哪个三角形来计算正方形的大小和方向。

我们可以画一条以a到b为基线的直角三角形，方法是在该线的中间画一个中心为m的圆，半径为a到m的距离：

该圆上的任何点都与a和b形成一个直角三角形。我们可以使用这个事实来计算树路径中点的坐标。

给定基线，我们开始构建树。首先，我们使用先前定义的多边形函数计算正方形的点。最后一点与第一点相同，因此我们对此不感兴趣，并将其绑定到匿名变量（_）：

下一步，我们需要构造一个带有斜边（p3，p4）的直角三角形-斜边是直角三角形的最长边。我们可以通过先将线（p3，p4）缩放0.5来实现，以得到从p3到该线中间的一条线。为了构造圆，我们用新函数flipLine翻转那条线的方向（通过交换端点）：

现在，我们将线r旋转零到Pi之间的任意角度，以获得直角三角形的第三点。在这里，我们使用0.7 * pi，它恰好是用于构造第一个示例树的角度。

然后，线（p4，p5）和（p5，p3）形成了树的递归构造的下一次迭代的基线：

在我们的程序中，我们不想硬编码旋转角度，而是将其作为参数传递。将所有这些步骤组合成一个递归函数，我们得到

fractalTree ::浮点数-＆gt;整数->行-＆gt; PathfractalTree因子n line = fractalTree＆＃39; n行，其中fractalTree＆＃39; 0行= [] fractalTree＆＃39; n行= [p1，p4] ++ fractalTree＆＃39; （n-1）（p4，p5）++ fractalTree＆＃39; （n-1）（p5，p3）++ [p3，p2]其中-行flipLine ::行->的翻转方向；线flipLine（pS，pE）=（pE，pS）[p1，p2，p3，p4，_] =多边形4线r = flipLine（scaleLine 0.5（p3，p4））（_，p5）= rotateLine（系数* ）

此函数的结构与kochLine的结构相同，其中通过使用多边形来获取多边形的角点而混合了一些kochFlake（尽管这里我们使用正方形，在kochFlake中使用了等边三角形）。而且，fractalTree仅是二进制递归的-即它包含两个递归调用-而kochLine是四向递归。

如果将n等于1传递给fractalTree，则它将返回正方形的三行，因为n == 0的递归调用将返回空路径。在本节开始处的第二个和第三个示例树是使用此函数的变体生成的，该函数在每三次和第五次迭代中分别将旋转因子更改为1-因子。以下截屏视频演示了如何在代码中实现这些变化。

还有许多其他可能的变化，例如，使用不直角的三角形作为基础，循环经过一系列不同的因素，或添加色彩效果。在本文中，为结束本章，对这些变体进行了少量选择。

实现一个函数colouredFTree :: Float->整数->颜色-＆gt;行-＆gt;通过接受树的颜色作为附加参数，在fractalTree上详细阐述的图片。

通过使用我们在螺旋射线的上下文中讨论的淡入淡出功能来改变colouredFTree

......