摘 要：摘要：递归是计算机科学和数学中的一个极其重要的问题求解工具。利用递归可以定义语言的语法，编写链表和树结构的查找和排序算法。递归函数即自调用函数，在函数体内部直接或间接地自己调用自己，也即函数的嵌套调用是函数本身。本文就C/C++时常利用递归算法解决一些实际问题做了重新探讨。
关键词：关键词：递归算法；递归函数；汉诺塔问题；函数调用
中图分类号：TP312 文献标识码：A 文章编号：
递归（Recursion）是一种有效的算法设计方案。递归算法的目的就是用一种普遍的统一规律来解决步骤繁多的问题，也正是因为如此，它是数据结构中一个“杀伤力”很大的算法，数据结构中的很多问题利用它可以清晰简洁地解决，由于递归算法涉及到数学归纳法的分析手段，所以，很多书籍都该算法做了分析。（1）
1. 递归的定义
如果要求幂函数Xn，其中X为实数，而n为非负整数，一种典型的做法是用X的n次重复乘积：
Xn = X * X * X * X * X * … * X （一共n个X连乘），
再如函数S（n）是计算前n个正整数的和，此问题可以用重复加的方法解决：
遇到上面类似的问题，大多数人会自然而然利用其数学含义去直接计算，而不会想到“递归”。对于求S（10），可以这样写S（10）= 1 +2 +3 + … + 10 = 55，如果我们想利用同样的方法计算S（11），则以上的加法会被重复一遍。其实，有一种更实际的方法是：使用前面的结果S（10）并加上11就得到了S（11），即：
S（11） = S（10） + 11 = 55 + 11 = 66 ，
该方法就是利用了前一次用较小值计算出的结果，从而求出了答案。我们称其为递归过程。
现在，我们重新回到幂函数，并将其作为递归过程来编写解决方案。求2的后续幂值时，注意到前次幂值可以被利用来计算下次幂值。例如：
23 = 2 * 22 = 2 * 4 = 8 ，
24 = 2 * 23 = 2 * 8 = 16 ，
一旦我们有了2的初始幂值（20 = 1），其后续各幂次的值只需将前次幂值乘2即可。用小的幂次值计算出另一值的过程便导致了幂函数的递归定义。对于实数X，Xn的值有下式得出：
同样，可以用类似的递归定义描述函数S（n），其功能是求前n个整数的和。最简单的情况是S（1）= 1。一般情况下，我们可以用前n-1个整数的和S（n-1），求解出S（n）：
如果解决问题的方法是把一个问题分解较小的子问题，并且将这些小问题可以用同样的算法解决，那么就可以用递归。当分解到可以直接处理的比较简单的子问题时，分解过程即终止。我们称这些子问题为终止条件，递归方法运用的就是“分而治之”的策略。
下面我们给出一般的递归定义，如果一种算法的定义组成如下，则它就是递归的：
①对应于某些参数可以求值的一个或者多个终止条件。
②一个递归步骤，它根据先前某次值，而求得当前值；递归步骤最终必须导致终止条件。
例如，幂函数的递归定义只有一个终止条件，那就是n=0的情形（X0 = 1）。递归步骤中描述了一般情况：
Xn = X * X（n-1）， n>0，
2. 问题的提出
递归的强大功能使得许多问题有非常简单而优雅的解决办法。我们拿一个非常经典的汉诺塔（Tower of Hanoi）问题，来说明如何利用递归进行问题求解的技术。
喜欢玩智力游戏的人很久以来一直着迷于汉诺塔问题，这个问题有众多版本的传说，而其中一个是这样描叙的。传说，布拉马圣殿（Temple of Brahma）里的教士们有一黄铜浇铸的平台，上立3根金刚石柱子。X柱子上堆放了64个金盘子，每个盘子都比其下面的盘子略小些。当教士们将盘子全部从X柱移动到Z柱以后，世界末日就来临。当然，这个问题还有一些限制条件，那就是在柱子之间一次只能移动一个盘子，并且任何时候大盘子都不能放到小盘子上。简单分析下，从X柱移动64个盘子到Z柱，共需要264-1次操作。假设1秒钟移动一次，那么共需约5000亿年以上时间。
这是一个经典的递归问题，智力游戏爱好者可能会被汉诺塔问题难住。但是，借助计算机的高速运算能力，我们可以用递归迅速解决这道题。为方便讨论，我们先用带5个盘子的柱子演示这个问题。我们将先把4个盘子移动到Y柱子上，然后再把最大的盘子移动到Z柱子上。
这样，问题就简化成仅仅将4个盘子从Y柱移到Z柱。用同样的方法，我们只需要将上面3个盘子先移走，然后将大盘子从Y柱移到Z柱上。接着，我们要移动的只剩下3个盘子，周而复始下去，直到只剩下一个盘子时将它移到Z柱上。
这个问题在运用递归求解时，它将问题分解成若干同样类型的小问题，移动一个盘子的简单操作就成了终止条件。
3. 设计递归函数
因递归函数是反复调用自身，所以在设计递归函数是需要注意以下几点：
①须有完成函数任务的语句；
②一个确定是否能避免递归调用的测试；
③一个递归调用语句；
④先测试，后递归调用。
我们先看一个简单的例子：求非负整数N的阶乘Factorial(N)，递归函数的结构可以用计算非负整数的阶乘进行说明。为了增强说明效果，我们同时写出该函数的递归算法和循环算法。阶乘Factorial(N)被定义为，所有小于或者等于N的正整数的积。若用N!表示阶乘，则
N! = N * (N-1) * (N-2) * … * 2 * 1,
例如，Factorial(6) = 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720,
Factorial(0) = 0! = 1, //特殊情况，终止条件
用循环实现该函数的方法如下：如果n为0则返回1，否则使用循环将连续各项进行相乘。
// 阶乘的循环算法
long Factorial(long n)
{ int prod = 1, i;
//若n==0返回prod=1；否则计算机prod = 1 * 2 * 3 * …* (n-1) * n的值
if (n>0)
for (i=1; i<=n; i++) prod *= i;
else return prod;
}
考察一下阶乘的不同例子中的各项，就可以得到它的递归定义。对于4!,第一项为4，而剩余各项（3*2*1）为3!。对于6!，结果也类似，它可以由6与5!的相乘得到。
那么，任何非负正整数N的阶乘递归定义包含一个终止条件和递归步骤：
由此，对于非负整数N的阶乘递归算法，可这样设计：
long Factorial( long n )
{ if (n==0) return 1; //终止条件为n==0，
else //递归计算
return n*Factorial(n-1);
}
从上面的阶乘问题我们看到，递归函数的主体解决的关键问题是：假设N-1步已经解决了，如何解决第N步。我们再回头看汉诺塔问题，它的运算规模随盘子的数量变化成几何级数增加，假设我们已经把N-1个盘子按照规定从X移到Z上，这一来，意味着我们也能按照规定把它们从X移到Y上。再进一步，我们可以把它们从X移到Z再移
到Y，甚至再移回到X，这时候我们会发现原来它们已经可以看作一个整体移到任何一个柱子上（只要第N个盘子在最下面）。这就是前面提到的数学归纳法分析中，利用了“假设”这一条件。当然，为了使算法简单，需要考虑用比较少的步骤解决这个问题。所以，先把N-1个盘子从X移到Y，然后把第N个盘子移到Z，最后把N-1个盘子从Y移到Z。
由上面的分析我们可得求解n阶汉诺塔问题的递归函数：
void Hanoi( int n, char X, char Y, char Z)
/*将X柱上按直径由小到大且自上而下编号为1至n的n个圆盘，按规则搬到Z柱上，Y柱可用作辅助柱位。搬动操作move（X，n，Z）可定义为（c是初值为0的全局变量，对搬动记数）：
printf( “%i. Move disk %i from %c to %c n”, ++c, n, x, z);*/
{ if(n==1) move(X, 1, Z); //移动编号为1的圆盘从X移动Z
else {
Hanoi(n-1, X, Z, Y); //将X上编号为1至n-1的圆盘移动到Y；Z作辅助柱
move(X, n, Z); //将编号为n的圆盘从X移到Z
Hanoi(n-1, Y, X, Z); //将Y上编号为1至n-1的圆盘移到Z，X作辅助柱
}
}
4. 递归的评价
C/C++的编译器对调用函数和被调用函数之间的链接和信息交换是通过栈来完成的。通常，当在一个函数的运行期间调用另外一个函数时，在运行被调用函数之前，系统需要完成三件事： （1）将所有的实在参数、返回地址等信息传递给被调用函数保存；（2）为被调用函数的局部变量分配存储区；（3）将控制转移到被调用函数的入口。而从被调用函数返回调用函数之前，系统也应完成三件工作：（1）保存被调用函数的计算结果；（2）释放被调用函数的数据区；（3）依照被调用函数保存的返回地址将控制转移到被调用函数。当有多个函数构成嵌套调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制信转移必须通过“栈”空间来完成，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区；每当从一个函数退出时，就释放它的存储区，则当前正运行的函数的数据区必在栈顶，此可以参阅函数调用存储分配问题等相关资料。
一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是自身而已。因此，和每次调用相关的一个重要概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用不本函数为进入“下一层”，即第i+1层。反之，退出第i层递归应返回至“上一层”，即第i-1层。为了保证递归函数正确执行；系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需要的信息构成一个“工作记录”，其中包含了所有的实在参数、所有的局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶；每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，即“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。
实际上，在调用函数和被调用函数之间不一定传递参数的值，也可以传递参数的地址等。通常，每个程序设计语言都有它自己约定的传递方法（包括被调用函数的执行结果如何返回调用函数等问题）。
在C/C++下允许使用递归，由于递归函数反复调用自身，导致系统创建了一个庞大的栈内存空间。递归的目的是简化程序设计，使程序易读。但递归增加了系统开销：时间上，执行调用于返回的额外工作要占用CPU时间；空间上，因为调用函数和被调用函数之间的链接和信息交换需要通过栈来进行，随着每次递归一次，栈内存就多用一截。所以，一个简单的递归函数也可能严重损害运行性能，更严重的是，一次递归调用可能产生一层接一层的递归调用，这会超出程序员的控制，并且对堆栈的需求也会超出可用栈空间范围。
5. 结束语
通常，在时间和空间上递归开销较大，它并非是解决问题的高效方法，但递归仍然是一个重要的设计和编程工具。许多算法用递归更便于叙述和解决，它们很自然地就可以用终止条件和递归步骤实现递归。虽然递归不是面向对象的概念，它却具有面向对象程序设计所具有的好处。它允许程序员管理算法中的一些关键逻辑部件而隐藏其复杂的实现细节，使得代码结构清晰，程序易懂，而且正确性容易得到证明。关于何时使用递归没有硬性规定，随着计算机硬件性能的不断提升，程序在更多的场合应优先考虑可读性而非高效。所以，鼓励用递归函数实现程序思想。
参考文献：
1、王士元. C高级实用程序设计. 北京：清华大学出版社. 1999
2、白帆，王隆. C语言开发实例详解. 北京：电子工业出版社. 1999
3、刘卫东，沈官林译，严蔚敏审. 数据结构C++语言描述. 北京：清华大学出版社. 2002
4、严蔚敏，吴伟民. 数据结构. 北京：清华大学出版社. 2001
5、钱能. C++程序设计教程. 北京：清华大学出版社. 2000
