分类： C/C++
2008-05-29 17:30:03
c++递归用法
ajin2k
“递 归”在C++中主要解决具有树型特征的算法或数据结构，递归的利用可以使算法或数据结构大大简化，代码简洁明了，相同一个具有该特性的课题采用递归或其他 算法，所要求的预定义及相应的结果都将不一样，用了递归可能使用减少部份定义，代码实现部份大大减少，一看便知。下面是一个从数据库中取数的例子对比：
实现中所使用的数据结构（表结构）
| 序号 | 英文名 | 中文名 | 类型 | 说明 |
| 1 | Id | 权限ID | Int | |
| 2 | ParentId | 父权限ID | Int | 用于指定父结点 |
| 3 | Name | 权限名称 | Varchar(32) | |
| 4 | IdCode | 菜单项ID | int | 权限与菜单项关联 |
由数据结构可以看出，通过ParentId，实现权限的树状结构，来描述权限的层次关系，这是一个典型的树型特征的数据结构，采用递归可以简化程序的实现 过程，但通过实验证明简单的采用递归将导致性能上的不足，运行效果无法满足用户的基本操作，在实现递归算法的后面将描述本程序在实现递归中作了相应的处 理。
１、通过对树结点的记忆来实现假递归
DWORD dwFunction = 0; //功能ID
HTREEITEM hItemLayer[5][2]; //用于保存当前正在操作的结点，用于回溯
int nIdCollection[5][2]; //保留父层结点的ＩＤ，用于识别下一个结点的父层所属
// 设置树根
hItemLayer[0][0] = m_treeOperatorPermission.InsertItem(_T("权限设置",3,3);
m_treeOperatorPermission.SetItemData (hItemLayer[0][0] , dwFunction);
hItemLayer[0][1] = hItemLayer[0][0];
nIdCollection[0][0] = 0; //父层ID
nIdCollection[0][1] = 0; //当前层ID
int nCurParentLay = 0;
CADORecordset collection(&m_conn); //ADO对象，用于从数据库取出记录集
CString strSQLString("select id ,ParentId , Name , IdCode from tbl_function order by id , parentid";
if(collection.Open (strSQLString))
{
int nCount = collection.GetRecordCount ();
CString strFunctionName;
for(int i = 0;i
{
//从数据库中取出结点数据
collection.GetFieldValue ("Name" , strFunctionName);
int nId;
int nParentId;
collection.GetFieldValue ("Id" , nId);
collection.GetFieldValue ("ParentId" , nParentId);
do
{
//判断其保留的父结点是否一致，用于判断是否从当前插入子结点，还是从父结点插入子结点
if(nParentId == nIdCollection[nCurParentLay][0])
{
//向父层插入子结点，并保留当前结点数据，用于回溯
hItemLayer[nCurParentLay][1] = m_treeOperatorPermission.InsertItem ((LPCTSTR)strFunctionName
, 0 , 1 , hItemLayer[nCurParentLay][0]);
nIdCollection[nCurParentLay][1] = nId;
m_treeOperatorPermission.SetHalfChecked (hItemLayer[nCurParentLay][1]);
dwFunction = nId;
m_treeOperatorPermission.SetItemData (hItemLayer[nCurParentLay][1] , dwFunction);
}
else if(nParentId == nIdCollection[nCurParentLay][1])
{
//在当前层建立子层
hItemLayer[nCurParentLay + 1][1] = m_treeOperatorPermission.InsertItem ((LPCTSTR)strFunctionName , 0 , 1 , hItemLayer[nCurParentLay][1]);
hItemLayer[nCurParentLay + 1][0] = hItemLayer[nCurParentLay][1];
nIdCollection[nCurParentLay + 1][0] = nParentId;
nIdCollection[nCurParentLay + 1][1] = nId;
m_treeOperatorPermission.SetChecked (hItemLayer[nCurParentLay + 1][1] , FALSE);
dwFunction = nId;
m_treeOperatorPermission.SetItemData (hItemLayer[nCurParentLay + 1][1] , dwFunction);
nCurParentLay ++;
}
else
{
//回溯，用于找到相匹配的父结点，便于插入结点
nCurParentLay --;
continue;
}
break;
}while(true);
collection.MoveNext ();
}
m_treeOperatorPermission.Expand (hItemLayer[0][0] , TVE_EXPAND);
}
collection.Close ();
m_treeOperatorPermission.ClearALLCheck ();
return 0;
点评：这种方法是通过状态的方法来实现递归的变相方法，可以看出在代码实现方面相当复杂，程序员必须详细注明其实现过程，才能够使其他程序员读懂（当然注释本来就是应该的，这里所说的是如何让其他程序更容易看懂代码）。
本程序中采用保留从父结点到当前结点的路径，用于回溯找到下一个结点的父结点，程序员是费尽心机，在他走过的足上做个标签，便于他回去是可以认得路，也便于摸索下一条路时不会重复走同样的一条分支（形成死循环）。
优点：该程序只用到一条检索语句即实现权限树的初始化，减少数据库连接数，从而在性能上将会是最优，即实现最其本的数据操作。
缺点：在点评中已经说到，代码的复杂性，给代码隐患的存在带来了很大的可能性，另外对数据也有一定的要求，必须符合一不的顺序才能够被正确执行。
c++递归算法（2）
２、递归算法的应用
long InitDefaultPermissionTree(int nParentId ,HTREEITEM hItem)
{
CString strSQLString;
strSQLString.Format ("select id , name from tbl_function where parentid = %d" , nParentId);
CADORecordset collection(&m_conn);
if(collection.Open (strSQLString))
{
//将所有数据取出
CArray
CArray
int nCount = collection.GetRecordCount ();
for(int i = 0;i < nCount ;i ++)
{
int nId;
CString strName;
collection.GetFieldValue ("id" , nId);
collection.GetFieldValue ("name" , strName);
collection.MoveNext ();
nIdArray.Add (nId);
strNameArray.Add (strName);
}
collection.Close ();
//将从数据库中取出的数据插入到树图上
for(i = 0;i < nCount;i ++)
{
int nId = nIdArray.GetAt (i);
HTREEITEM hSonItem = m_treeOperatorPermission.InsertItem (strNameArray.GetAt (i) , 0 , 0 ,
hItem);
m_treeOperatorPermission.SetItemData (hSonItem , nId);
//后面讲述采用m_TreeDataMap(CMap
m_TreeDataMap.SetAt(nId , hSonItem);
//对当前结点进行递归插入子结点数据
InitDefaultPermissionTree(nIdArray.GetAt (i) , hSonItem);
}
}
return 0;
}
点评：在本程序中简单地看去，只用了一个循环即完成数据的读取与显示（本程序采用两个循环只是想减少由于递归而增加数据库连接数），显而易见，代码清晰易懂。不需要太多的注释便可明白其中的实现过程。
在实现过程中没有象第一个例子的那样具有相当多的辅助变量来帮助记忆树的结构，这个实例由递归的特性来完成。
优点：简洁明了，通俗易懂，最大的特点就是执行递归时对其实现的默认，这也是在编写递归程序时应该具备的基本思想认识，不然程序员绝对想不到该算法是可以用递归来实现的。
缺点：第一例中已经说到的优点，其实也就是本例的缺点，递归所产生相应的出入栈操作及相当的其他数据（如数据库连接数等）都将对程序的性能产生负面影响， 特别对于层次较多的情况则更为严重，当然对于非树型特征的不提倡采用递归的实现算法，如求1～100的累加时，虽然可以用递归算法可以实现，但它仍然可以 用常规算法来实现，这里就不提倡递归算法。
正常算法
Int Sum(int nMax)
{
int nSum = 0;
for(int I = 1;I <= nMax;I ++)
{
nSum += I;
}
return nSum;
}
递归算法
Int Sum(int nMax)
{
if(nMax > 0)
{
return Sum(nMax – 1) + nMax;
}
else
{
return 0;
}
}
综上所述，递归算法应该用于某些采用常规算法实现较为困难、并且具有递归特征的算法才会采用递归算法，否则不建议变相应用递归算法，如后面所述的计算1～100的累加，这里就是坚决否定递归算法的应用。
编写代码应该考虑多方面因素，包括代码的可读性、可理解性、简单性（这个特性有一定的局限性）、执行性能等因素决定。
对于一个性能要求不高但采用递归可以提高代码的可读性与可理解性并且可以大大简化代码的实现过程，递归将是首选。
对于执行性能要求较高时，可能要求程序员采用其他类似的算法来替代，确保性能优先，但部份情况，采用其他算法来替代递归未必能够提高算法的性能，反而递归是最佳算法（一般指需要的递归层次较少）。
总之，使用递归有其利，也有其弊，程序员在实现过程中是否应该采用递归算法，应考虑采用递归算法是否会影响相关模块或系统的整体要求。
