递归的应用 -- 最简单分形图形实现


作者：吉林大学　胡卓玮

下载本文源代码


图一 例子代码运行结果

    大家在C/C++学习时都会遇到递归，课本上以汗诺塔为例进行讲解，然后大家都希望自己找到一个递归的实例。本文以一个最简单的分形图形来讲解递归的实现过程。
    先来看看绘制这个分形图形的思路。如图二所示，给定两点（p1和p2）确定一条直线，计算这条直线的长度，如果长度小于预先设定的极限值则将这两个点用直线相连，否则，取其1/3处点（点1）、2/3处点（点2），以及中点上方一个点（点3），这个点与第1点、第2点构成的直线与直线p1p2的夹角为60度。判断这五个点按照顺序形成的四条直线的长度是否小于预先设定的极限值，如果小于，则在将相应的两个点相连在屏幕上显示一条直线，否则继续对相应两点形成的直线进行以上判断。


图二 分形图形实现示意图

    这是一个典型的递归问题。我们可以看看如果不使用递归该怎样得到我们需要的结果。首先需要设立一些变量来存储点的坐标，由于不使用递归，我们需要在整个过程的最后，把计算所得并保存起来的点的坐标传递给画线的函数，在不满足递归过程结束的条件下（即直线的长度大于极限值），将需要增加三个点，这时是四条直线，如果下一次仍然达不到结束条件，将会得到的点数为2 + 3 + 4 * 3，直线数为4^2。这样，对于第n次不满足结束条件后获得的点数为：2 + 3 + 3 * 4 + 3 * 4 ^ 2 + …… + 3 * 4 ^ (n - 1)，直线数为4 ^ n条。随着n的增大，这不是一个小数目。但如果使用递归实现，情况会大不一样，不需要定义过多的变量，不需要考虑复杂的点的顺序关系。
    来看看我们的程序当中是如何利用递归实现这个简单的分形图形的。整个实现过程封装到类KSQXClass中，为了方便点坐标的存取，定义了KSQXPoint类，参看文件KSQXClass.h和KSQXClass.cpp，大家可以看到类的具体定义和实现。
    整个递归过程用函数Draw来实现。参数含义如下：
CDC* pdc; //设备描述表，绘制分形图形的设备
KSQXPoint p1, KSQXPoint p2;　//直线的起点和终点，KSQXPoint以点的x,y坐标作为成员变量
    一开始需要计算直线的长度并判断其长度是否小于极限值：

 ds = (float)sqrt(dx * dx + dy * dy); if(ds <= m_limit) { 　pdc->MoveTo((int)p1.m_x, (int)p1.m_y); 　pdc->LineTo((int)p2.m_x, (int)p2.m_y); 　return; }

 Draw(pdc, p1, tempp1); Draw(pdc, tempp1, tempp3); Draw(pdc, tempp3, tempp2); Draw(pdc, tempp2, p2); 

 KSQXClass myksqx; KSQXPoint p1, p2; p1.m_x = 100; p1.m_y = 300; p2.m_x = 400; p2.m_y = 300; myksqx.SetLimit(1); CDC* pdc; pdc = GetDC(); myksqx.Draw(pdc, p1, p2);