Scratch用递归画谢尔宾斯基三角形

Intoweb

递归是学习编程中的一个难点，它的含义是：编程语言中，函数直接或间接调用函数本身，则该函数称为递归函数。

换个通俗说法就是：从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，故事讲的是：从前有座山……这样讲下去是不是没有尽头了，在实际编程中递归要设置一个递归出口，否则就成了死循环。

另外俄罗斯套娃也可以看作递归，娃娃里面套着娃娃……直到最小的娃娃（递归出口）。

初步了解了递归思想后，我们通过画分形图来体验一下递归的效果。

谢尔宾斯基三角形（Sierpinski triangle）是一个优美的分形图案。从一个大三角形开始，连接每一个边的中点，将大三角形分为四个小三角形，然后挖掉中间的三角形，依次对其余三个三角形重复执行上述操作，用Python绘制的效果如图1，为了区分不同层级的三角形使用了不同的颜色。因为对三角形不断重复进行分割操作，使用递归就能让计算机画出这个图形了。

这是Scratch 绘制谢尔宾斯基三角形的代码（如图2）。由于递归函数需要引用本身，所以必须要用到自定义积木，这样就可以在自定义积木中插入自身完成递归。

1. 自定义积木“谢尔宾斯基三角形（边长）”。首先判断如果边长>4就继续执行，因为理论上后面的步骤2和3可以无限重复下去，就代码而言，必须要保证算法的有穷性，通过设置边长的最小值，程序就可以按需要终止。根据Scratch画笔的精度，最小的三角形边长大于4时，图形效果較好。你可以自行试验最小边长为3的效果，最小的三角形成实心的了。如图3从左到右，不断细分的谢尔宾斯基三角形（如图3）。

2. 重复执行3次，移动“边长”，左转120度，画出一个三角形。

3. 为了画出更小一级的三角形，调用自身，并将边长除以2。因为在重复执行3次的循环内，所以可以画出3个二分之一“边长”的三角形。

4. 由于递归引用，所以三角形边长会持续减半，实际执行时设置边长为200，会从最小边长为6的三角形开始画，逐渐画出最大边长200的三角形。实际绘制效果，如图4。

通过绘制谢尔宾斯基三角形，我们初步接触了在自定义积木中引用本身的结构。这就是递归函数。递归概念是比较难以理解和用好的。未来我们将继续对这个概念进行更深入的学习。