李杰黑龙江省政法管理干部学院150080
摘要：递归算法是一种直接或者间接地调用自身的算法。在计算机程序编写中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。文中一方面结合汉诺塔问题和N皇后问题等经典实例介绍了递归程序设计的一般步骤和方法，还介绍了如何通过分治和回溯等策略进行递归程序设计。
关键词：递归数据结构算法实现
一、引言
递归在程序设计基础、数据结构以及算法设计与分析等课程的教学中都占用重要地位，是一类重要的程序设计方法。但递归教学一直是个难点，学生通常会对为何用递归、如何用递归以及递归程序的执行过程存在疑惑。
本文旨在解决这一问题，全文以递归为中心，从什么是递归、为何用递归、如何用递归以及使用递归需要注意的问题四个方面组织全文，从方法论的角度对递归程序设计进行了系统的阐述。
二、递归程序的实现策略
进行递归程序设计的关键是借助递归关系的定义和递归边界构造递归函数，但有些问题的描述中递归关系和递归边界并没有显示给出，称此类问题为隐式递归问题。
对于显式递归问题，如前所述，直接根据递归关系的定义和递归边界构造出递归函数即可求解；对于隐式递归问题则要通过一定的策略来找出隐藏的递归关系和递归边界，常见策略如降阶、分治和回溯。
三、递归算法的特点
递归算法是一种直接或者间接地调用自身的算法。在计算机程序编写中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点：
1.递归就是在过程或函数里调用自身。
2.在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
3.递归算法解题通常显得很简洁，但递归算法解题的运行效率较低，所以一般不提倡用递归算法设计程序。
4.在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
四、递归算法的要求
递归算法所体现的“重复”一般有三个要求：
1.每次调用在规模上都有所缩小（通常是减半）。
2.相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。
3.在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
五、递归算法典型问题——汉诺塔问题
代码如下：
#include<stdio.h>
voidmove(intn,chara,charb,charc)
{
if(n==1)
printf("\t%c->%c\n",a,c);//当n只有1个的时候直接从a移动到c
else
{
move(n-1,a,c,b);//第n-1个要从a通过c移动到b
printf("\t%c->%c\n",a,c);
move(n-1,b,a,c);//n-1个移动过来之后b变开始盘，b通过a移动到c，这边很难理解
}
}
main()
{
intn;
printf("请输入要移动的块数：");
scanf("%d",&n);
move(n,'a','b','c');
}
1.分治。若操作对象可定义成由若干结构相同但规模更小的部分组成，则对原对象的操作可递归分解到其各组成部分上分别进行，如此递归分解直到不可再分时停止，此类求解策略称为分治。根据分治策略很容易得到相应的递归关系定义和递归边界，从而构造出具体的递归函数。
如非空的二叉树可看作为由根结点、根节点的左子树以及根结点的右子树三部分组成，每一部分又都是一颗树。如右图所示二叉树T（图略）可看作由根节点A、结点B、C构成的左子树和结点D、E、F构成的右子树组成。欲设计递归函数NodeCount(T)求二叉树T的结点总数，显然T的结点数是T的左子树结点数与T的右子树结点数之和再加1，这实际就是递归关系的定义：
intNodeCount(BiTreeT)
{intn;
if(T==NULL)
n=0;
else
n=NodeCount(T->lchild)+NodeCount(T->rchild)+1;
returnn;}
再注意到空树的结点数为0，依此作递归边界，即可得到表4（略）所示的树结点计数的递归函数。
2.回溯。回溯也是一种问题求解策略，通常指让计算机从某种可能的情况出发自动向前进行搜索，碰到符合的情况就输出或者保存起来，在一条路径上走到“尽头”后就回到原来的岔路口选择一条以前没有走过的路重新向前进行探测，直到找到解或者走完所有路径为止。回溯具体编程实现时通常都用递归：“向前进行搜索”对应递归调用，“尽头”对应递归边界。
比如N皇后问题。题目是说，一个N*N的国际象棋棋盘上主放置N个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行、同一列、同一条斜线上，要求输出所有可能的摆放方案。其实，题目就是要找出所有可能的合法情况，可以考虑用回溯法求解。
让计算机逐行前进，每行摆放一个棋子，若合法则前进到下一行。为此可设递归函数voidNQueens(intarr[N][N],inti);第一个参数代表棋盘，第二个参数代表目前标号为0的行到标号为i-1的行已经各有一个棋子，且符合规则要求。递归函数第一次被调用时形参i值应为0,函数体内递归调用语句应为NQueens(arr,i+1)。至此递归关系定义已经找到，但还有一个问题，即递归何时停止或者说计算机前进过程中如何判断是否“走到尽头”。分析可见共有两种情况：其一，当前行下完一个棋子后出现了非法情况，如同一列或同一斜线上出现了多个皇后，此时应抹掉该行所下棋子，在其右侧重新下一个棋子再重新检查；其二，当前行下完一个棋子后仍然合法，但恰巧当前行是最后一行，这实际意味着已经得到了一种合法的摆放方案，此时应输出该方案，之后抹掉该行所下棋子，在其右侧下一个棋子重新检查。由上述递归边界和递归关系定义可构造递归函数如下:
voidNQueens(intarr[N][N],inti)
{for(intj=0;j<n;++j)
{arr[i][j]=1;
if(Verify(arr,i)==0){arr[i][j]=0;continue;}
elseif(i==N-1){PrintChessBoard(arr);arr[i][j]=0;continue;}
else{NQueens(arr,i+1);arr[i][j]=0;continue;}}}
通过上例可见，回溯法的主要特点是递归结束的条件在搜索的最后一步，关键是找到递归边界条件。
3.递归存在的问题。使用递归进行程序设计思路清晰、代码简洁，但递归调用过程中，每一次发生调用系统都要将返回地址、局部变量等信息入栈保存，因此，递归程序的运行效率较低，而且递归次数过多还容易造成栈溢出。此外，尤其要避免重复递归调用的现象发生。
比如求Fibnacci数列的第n项可通过递归函数实现：
longf(intn)
{intr;
if(n==1n==0)r=1;
elser=f(n-1)+f(n-2);
returnr;}
假设n=4则递归执行过程中发生的递归调用如图3（略）所示，可见n=4时f(1)已经被重复调用了3次。在Core2CPUT5500、内存1G的机器上进行测试，计算f(40)约需20.374秒的时间，其主要原因在于计算f(40)时f(1)会被重复调用165580141次；而计算f(50)更是需要40多分钟！
六、结语
本文系统讲述了递归的基本概念、使用递归进行程序设计的好处以及如何设计递归程序，结合Hanoi塔问题、N皇后问题等经典实例介绍了通过降阶、分治及回溯构造递归函数的一般化方法，并对递归使用过程中可能存在的问题进行了说明。总得来说，递归作为一种重要的程序设计方法可使得编码清晰易懂，但存在运行效率较低的问题，在实际应用当中，建议仅当传统方法不方便求解时使用递归。
参考文献
[1]杨文鹏贺兴时杨选良编著新编运筹学教程——模型、解法及计算机实现.西安：陕西科学技术出版社，2005。
[2]王惠文著偏最小二乘回归方法及其应用.北京：国防工业出版社，2000。