摘 要：递归是一种重要的程序设计方法，但在教学过程中一直是个难点。本文从方法论的角度对递归程序设计进行系统的阐述，介绍了递归程序设计的一般步骤和方法，以及如何通过分治和回溯等策略进行递归程序设计。
关键词：递归；数据结构；算法实现
1、引言
递归在程序设计基础、数据结构以及算法设计与分析等课程的教学中都占用重要地位，是一类重要的程序设计方法，但递归教学一直是个难点。学生通常会对为何用递归、如何用递归以及递归程序的执行过程存在疑惑。本文旨在解决这一问题，全文以递归为中心，从什么是递归、为何用递归、如何用递归以及使用递归需要注意的问题四个方面组织全文，从方法论的角度对递归程序设计进行系统的阐述。文中一方面结合汉诺塔问题和N皇后问题等经典实例介绍了递归程序设计的一般步骤和方法，还介绍了如何通过分治和回溯等策略进行递归程序设计。
2、 递归程序的实现策略
进行递归程序设计的关键是借助递归关系的定义和递归边界构造递归函数，但有些问题的描述中递归关系和递归边界并没有显示给出，称此类问题为隐式递归问题。
对于显示递归问题，如前所述，直接根据递归关系的定义和递归边界构造出递归函数即可求解；对于隐式递归问题则要通过一定的策略来找出隐藏的递归关系和递归边界，常见策略如降阶、分治和回溯。
2.1 分治
若操作对象可定义成由若干结构相同但规模更小的部分组成，则对原对象的操作可递归分解到其各组成部分上分别进行，如此递归分解直到不可再分时停止，此类求解策略称为分治。根据分治策略很容易得到相应的递归关系定义和递归边界，从而构造出具体的递归函数。
如非空的二叉树可看作为由根结点、根节点的左子树以及根结点的右子树三部分组成，每一部分又都是一颗树。如右图所示二叉树T可看作由根节点A、结点B、C构成的左子树和结点D、E、F构成的右子树组成。欲设计递归函数NodeCount(T)求二叉树T的结点总数，显然T的结点数是T的左子树结点数与T的右子树结点数之和再加1，这实际就是递归关系的定义：
int NodeCount(BiTree T)
{int n;
if(T= =NULL)
n=0;
else
n=NodeCount(T->lchild)+NodeCount(T->rchild)+1;
return n;}
再注意到空树的结点树为0，依次作递归边界，即可得到表4所示所示的树结点计数的递归函数。
2.2 回溯
回溯也是一种问题求解策略，通常指让计算机从某种可能的情况出发自动向前进行搜索，碰到符合的情况就输出或者保存起来，在一条路径上走到“尽头”后就回到原来的岔路口选择一条以前没有走过的路重新向前进行探测，直到找到解或者走完所有路径为止。回溯具体编程实现时通常都用递归：“向前进行搜索”对应递归调用，“尽头”对应递归边界。
比如N皇后问题。题目是说，一个N*N的国际象棋棋盘上主放置N个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行、同一列、同一条斜线上，要求输出所有可能的摆放方案。其实，题目就是要找出所有可能的合法情况，可以考虑用回溯法求解。
让计算机逐行前进，每行摆放一个棋子，若合法则前进到下一行。为此可设递归函数void NQueens(int arr[N][N],int i);第一个参数代表棋盘，第二个参数代表目前标号为0的行到标号为i-1的行已经各有一个棋子，且符合规则要求。递归函数第一次被调用时时形参i值应为0,函数体内递归调用语句应为NQueens(arr,i+1)。至此递归关系定义已经找到，但还有一个问题，即递归何时停止或者说计算机前进过程中如何判断是否 “走到尽头”。分析可见共有两种情况：其一，当前行下完一个棋子后出现了非法情况，如同一列或同一斜线上出现了多个皇后，此时应抹掉该行所下棋子，在其右侧重新下一个棋子再重新检查；其二，当前行下完一个棋子后仍然合法，但恰巧当前行是最后一行，这实际意味着已经得到了一种合法的摆放方案，此时应输出该方案，之后抹掉该行所下棋子，在其右侧下一个棋子重新检查。由上述递归边界和递归关系定义可构造递归函数如下:
void NQueens(int arr[N][N],int i)
{for(int j=0;j
if(Verify(arr,i)==0){arr[i][j]=0;continue;}
else if(i==N-1) {PrintChessBoard(arr);arr[i][j]=0;continue;}
else {NQueens(arr,i+1);arr[i][j]=0;continue;}}}
通过上例可见，回溯法的主要特点是递归结束的条件在搜索的最后一步，关键是找到递归边界条件
3、 递归存在的问题
使用递归进行程序设计思路清晰、代码简洁，但递归调用过程中，每一次发生调用系统都要将返回地址、局部变量等信息入栈保存，因此，递归程序的运行效率较低，而且递归次数过多还容易造成栈溢出。此外，尤其要避免重复递归调用的现象发生。比如求Fibnacci数列的第n项可通过递归函数实现：
long f (int n)
{int r;
if(n==1n==0) r=1;
else r=f(n-1)+f(n-2);
return r;}
假设n=4则递归执行过程中发生的递归调用如图3所示，可见n=4时f(1)已经被重复调用了3次。在Core 2CPU T5500、内存1G的机器上进行测试，计算f(40)约需20.374秒的时间，其主要原因在于计算f(40)时f(1)会被重复调用165580141次；而计算f(50)更是需要40多分钟！
4、结束语
本文系统讲述了递归的基本概念、使用递归进行程序设计的好处以及如何设计递归程序， 结合Hanoi塔问题、N皇后问题等经典实例介绍了通过降阶、分治及回溯构造递归函数的一般化方法，并对递归使用过程中可能存在的问题进行了说明。总地来说，递归作为一种重要的程序设计方法可使得编码清晰易懂，但存在运行效率较低的问题，在实际应用当中，建议仅当传统方法不方便求解时使用递归。
参考文献：
[1]谭浩强,C程序设计,清华大学出版社,北京：2005.7
[2]王晓东,计算机算法设计与分析,电子工业出版社,北京：2007.5
