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

大家在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;
      }
其中的极限值m_limit通过成员函数SetLimit设定。

如果ds大于极限值，进行以下工作。
计算点１、点２和点３的坐标。关于点的坐标的计算，这里不进行过多的讲解，读者对照程序代码去理解吧。
    这三个点的坐标得到以后，就可以组成四条直线：p1和1,1和3,3和2,2和p2，分别以这四条直线的起点、终点坐标为参数代入函数Draw中，进行递归调用。       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);      
程序运行结果如本文图一所示。
关于代码和文章中的问题大家可以和作者联系：
通信地址：吉林省长春市西民主大街６号地球探测科学与技术学院２００１级硕士研究生　胡卓玮
电子信箱：QiGi@vip.sina.com
欢迎访问作者的主页：forevergis.6to23.com