1. 引言
递归算法是一种直接或者间接地调用自身算法的过程,递归算法把大问题转化为规模缩小的同类问题的子问题,将一个复杂问题逐步简化并最终转化为一个最简单的问题,最简单问题的解决就意味着整个问题解决。递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解,为一些问题提供了最简单的解决方案 [1] 。递归算法简洁、规整,虽然在整体结构上易于理解,但在分析递归运行情况时,总给人不可捉摸、难以理解的感觉,主要原因是递归调用实现机制太抽象,递归函数层层跳转、回溯,使人们对递归算法的分析难以把握。
多年来,很多学者对递归算法的分析进行了深入研究,但还存在一些不足,文献 [2] [3] [4] 在讨论递归算法结果时,一般根据函数调用的过程直接分析,对于简单的问题容易实现,但对复杂递归函数分析就困难重重,分析过程过于抽象,极易出错;文献 [5] [6] 使用递推函数对递归算法分析研究,这种方法不具有通用性,而且一些递归算法难以转换为递推式;文献 [7] [8] [9] 提出了用递归树研究递归的方法,将递归与树进行映射,便于操作,但分析时局限于单棵树,注重于函数调用关系的研究,而递归调用中有时是多棵树组成的森林,递归树在处理这些问题时显得不足,且在树上标注,处理结构不清晰。
本文将森林引入递归算法的分析处理过程,解决递归算法分析中存在的问题,通过建立递归与森林的逻辑映射关系,根据对程序递归结构分析,判断树结构,由入口函数,建立搜索树,所建立的树不仅限于二叉树,根据实际问题可以是单分支树,可以是二叉树、多叉树,甚至多棵树,到达叶子节点进行回溯,将程序结构映射为森林,并根据执行情况建立状态调用表,既分析全面,又使分析结构清晰、结果准确,有效解决了递归算法结果分析中的难题。
2. 树在递归分析中的应用
递归算法整个过程分为两部分:递推和回归,递归调用由多个子递归构成,递归的结构和处理与树的特点很相似,树由多个子树构成,对树的遍历就是搜索和回溯的过程,所以在递归算法分析上可以将递归结构映射到树型结构上,可以用树结构进行递归算法的分析。实际问题中,存在一些分支语句中含有递归的情形,这时需要分成多棵树,多棵树组成逻辑上的森林。
森林为M棵互不相交的树的集合,表示为F = {T1, T2, ∙∙∙, Tm} [10] ,T1, T2, ∙∙∙, Tm为组成森林的树,可以将递归算法逻辑映射为森林,具体处理上以树为处理单元,建立标准的处理流程。
递归算法映射到树时,在分析中对树的遍历采用先根遍历,边界条件即为树的叶子节点,下面以一简单递归类型的程序结构为例,说明使用树对递归算法分析的过程,在第3部分采用具体实例进行详细说明:
(1)void Recursive (int m, int n)
{
(2) if (m==0)
(3) return ;
(4) if (n==0)
{
(5) a= Recursive (m-1,1);
(6) return a;
}
(7)else
{
(8) b= Recursive (m-1,n);
(9) printf(“%d %d”,m,n);
(10) c= Recursive (m,n-1);
}
}
2.1. 分析程序结构
首先分析程序的整体结构,函数Recursive为递归函数,作为树的基础节点,通过深度搜索对树节点进行扩展,每次递归函数执行过程的节点作为树的一个节点类型;其次要分析递归函数在程序结构中所处位置,语句(5)的递归函数与语句(8)、(10)的递归函数处于不同的语句结构体中,执行到语句(5)时程序跳转到另外一棵树,所以要分成两个不同的树进行处理,这两棵树构成森林;第三,语句(8)、(10)在一棵树中进行处理,处理过程扩展为二叉树,b和c处于二叉树的不同分支;第四,两个分支中的其他语句,如:程序中的处理语句(9)在b执行到叶子节点回溯到c的过程中执行。
程序中语句(2)、(4)为边界,搜索到叶子节点时执行,执行语句(4)时跳到另一棵树执行搜索;语句(1)为程序入口,可看作根节点。
2.2. 建立树型图
根据对程序结构的分析,明确树的总体结构,本示例为两棵树构成的森林,每棵树为二叉树,入口函数作为树的根节点,从根节点进行深度搜索,由搜索情况建立树节点,到叶子节点进行回溯。多棵树组成的森林,在搜索树节点时,根据实际情况进行树间跳转,根据搜索情况绘制树型图,标明节点序号。
2.3. 建立状态调用表
树只建立节点,根据节点扩展情况,对应树的节点建立对应状态调用表,调用表反映状态变化及其他语句块执行,一方面反映程序整体全貌,另一方面使分析更加清晰、直观;状态调用表主要内容有:节点编号、节点名、节点动作、节点值等,根据树的搜索情况建立该表,回溯节点前加H代表回溯动作,回溯到根节点,递归算法分析结束,结果为递归算法处理结果。
3. 实例分析
3.1. 汉诺塔问题
有A,B,C三根柱子,A柱上按大小顺序从下往上摞着n片圆盘,现在要将这些圆盘从A柱移至C柱,并保持上小下大的顺序。移动规则如下:每次只能移动一个盘,大盘不能放在小盘上。
程序主体结构:
void hanoi (int n,char a,char b,char c)
{
if(n==1)
{
printf(“%c-->%c”, a,c);//1
}
else
{
hanoi(n-1,a,c,b );
printf(“%c-->%c”, a,c);//2
hanoi(n-1,b,a,c);
}
}
递归分析:
将递归函数作为树的节点,程序中有两个递归函数分别为树的左右分支,左分支:hanoi(n-1,a,c,b),右分支:hanoi(n-1,b,a,c),其他处理语句单独列明:如:1语句在n等于1时执行,为出口语句,2语句在右分支前执行,在下述实例中只在4、5、7节点前执行。
假如初始调用为hanoi(3,'A','B','C'),则调用树结构如图1所示,执行过程调用状态如表1所示。
![](//html.hanspub.org/file/21-1541471x9_hanspub.png)
Figure 1. The tree structure of the Tower of Hanoi
图1. 汉诺塔执行的树结构
![](Images/Table_Tmp.jpg)
Table 1. The Tower of Hanoi call status table on execution procedure
表1. 汉诺塔执行过程调用状态表
3.2. 2018 noip普及组试题三(3)
int findans(int n,int m)
{
if(n==0) return m;
if(m==0) return n%3;
return findans(n-1,m)-findans(n,m-1)+findans(n-1,m-1);
}
将return findans(n-1,m)-findans(n,m-1)+findans(n-1,m-1),修改为:
f1= findans(n-1,m)
f2= findans(n,m-1)
f3= findans(n-1,m-1)
return f1-f2+f3
调用实例findans(1,2)
树为三叉树,第一分支为findans(n-1,m),第二分支为findans(n,m-1),第三分支为findans(n-1,m-1),函数简称为f(n,m)。
语句f1-f2+f3在第三分支后执行,return m,return n%3为出口语句。
调用树结构如图2所示,执行过程调用状态如表2所示。
结果为:3。
![](//html.hanspub.org/file/21-1541471x10_hanspub.png)
Figure 2. The tree structure of 2018 noip popularization group
图2. 2018 noip普及组树结构
![](Images/Table_Tmp.jpg)
Table 2. The call status table of 2018 noip popularization group
表2. 2018 noip普及组调用状态表
3.3. 阿克曼函数
阿克曼函数定义:
n+1m=0,n>0
A(m,n)=A(m-1,1) n=0,m>0
A(m-1,A(m,n-1)) n>0,m>0
程序主体结构:
int Ackerman(int m, int n)
{
if (m==0)
return n + 1;
if (n==0)
return Ackerman(m - 1, 1);
else
return Ackerman(m - 1,Ackerman(m, n - 1));
}
因为递归函数是参数,语句return Ackerman(m - 1,Ackerman(m, n - 1));修改为:
a= Ackerman(m, n - 1);
b= Ackerman(m - 1,a);
return b;
因为if语句含有递归函数,所以分为两棵树,树1称为t1,树2称为t2。t1有两个分支,左分支为Ackerman(m, n - 1),右分支为Ackerman(m - 1,a),函数简称为A(m,n)。t2有1个分支为Ackerman(m - 1, 1)。
入口调用函数为:A(1,2)
t1调用树结构如图3所示,执行过程调用状态如表3所示,跳转后的分支树t2的调用树结构如图4所示,执行过程调用状态如表4所示。
结果为:4。
![](Images/Table_Tmp.jpg)
Table 3. The call status table of T1
表3. T1树调用状态表
![](Images/Table_Tmp.jpg)
Table 4. The call status table of T2
表4. T2树调用状态表
4. 结论
当前对递归算法的分析方法主要有:根据函数调用的过程直接分析 [2] [3] [4] ,使用递推函数分析 [5] [6] ,这两种方法分析递归算法的局限性是显而易见的,在分析稍复杂的递归算法时是无能为力的;用递归树分析递归过程 [7] [8] [9] ,分析时局限于单棵树、状态调用过程不清晰;本文通过对递归不同类型典型实例的分析,将递归算法逻辑映射到森林,用树结构处理递归函数结果。给出了用森林分析递归函数的基本流程,通过分析程序结构、搜索建立分析树和状态变化对照表,到达叶子节点进行回溯,既分析全面,又使分析结构清晰、结果准确,有效解决了递归算法结果分析中的难题。