浅析递归函数在C++语言中的实现

陈颖鑫，李主国

（1.中南财经政法大学，湖北 武汉 430073；2.湖北广播电视大学，湖北 武汉 430073）

浅析递归函数在C++语言中的实现

1陈颖鑫，2李主国

（1.中南财经政法大学，湖北 武汉 430073；2.湖北广播电视大学，湖北 武汉 430073）

本文结合生活实际探讨了递归函数的概念，并举例说明了递归函数的具体编写方法，研究了递归的调用机制，最后总结了递归函数的利弊，提出要适当地使用递归思想的原则。

递归；函数；程序设计；C++语言

1 .引言

如果定义一个概念或事物需要用到这个概念或事物本身，我们称它的定义是递归的（Recursive）。例如，下面这个故事：

从前有座山，山上有座庙，庙里有个老和尚，正在给小和尚讲故事！故事是什么呢？“从前有座山，山上有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山上有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”

当听到这个故事，一般人都会感觉到无聊之极。然而，数学上确实需要这种“无聊”呢，例如，有很多概念是用它自己来定义的，像n的阶乘是这样定义的：n的阶乘等于n乘以n-1的阶乘。如果这样就算定义完了，恐怕跟上面那个故事有异曲同工之妙了：n-1的阶乘是什么？是n-1乘以n-2的阶乘。那n-2的阶乘又是什么？这样下去，永无休止了。因此，需要定义一个最关键的基础条件：0的阶乘等于1。

实质上，递归函数使用的是数学归纳法的理念，即初始条件和递推两者不可或缺。递归，是函数实现的一个很重要的环节或者方法，很多程序都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在调用的下级函数中调用自己，不管是直接调用，还是间接调用。

2 .递归函数编程

把上面的阶乘定义用C++语言来实现，可以写成这样：

从程序可以看到，我们采用递归函数的方法编程的时候，只需要把初始条件和递推两者表达清楚，基本上就可以完成任务了。计算机会根据你的合理设计，自行完成递归的算法过程。

不妨再来看几个问题：

A）Fibonacci数列，它是这样定义的：

①fib(1)=1

②fib(2)=1

（1）液质条件：Thermo Scientific LCQ液质联用仪，XbridgeTM-C18色谱柱（250 mm×4.6 mm，5 μm）；填充剂为十八烷基硅烷键合硅胶；流动相为乙腈-0.5%氨水溶液，等度洗脱（80∶20），体积流量0.5 mL/min；检测波长235 nm；柱温25 ℃；进样量5 μL。ESI离子源，正离子检出模式，扫描范围m/z 95～800。

③fib(n)=fib(n-1)+fib(n-2)

用C++语言编程的实现：

B）使用辗转相除法求两个正整数a和b的最大公约数：

①如果a能被b整除，则最大公约数是b。

②否则，最大公约数等于b和a%b的最大公约数。（a%b表示a被b除的余数）

用C++语言编程的实现：

上面两个问题看似毫不相干，它们之间却有一个有意思的联系（即Lamé定理）：如果辗转相除法需要k步来计算两个数的最大公约数，那么这两个数之中较小的一个必然大于等于Fibonacci数列的第k项。

C）猴子吃桃问题

猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩一个桃子了。试求第一天至少摘下多少桃子？

下面这个程序可以求出每天的桃子数目：

D）汉诺塔游戏

有三根柱子，在一根柱子上从下往上按照大小顺序摞着n片黄金圆盘。需要把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

使用C++语言可以这么实现：

上述若干问题均是以递归的形式描述的，所以很容易采用递归方法编程实现。从以上几个问题的求解可以看出，凡使用递归解法，一定要设置好初始条件，再就是对递归过程的处理。初始条件是递归得以完成的终结条件，而递归过程则是将复杂问题逐步简化为较简单一点的问题，直到归结为终结条件。

3 .递归程序的运行机制

递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝，这些拷贝和函数的其他执行过程毫不相干。这种机制依靠栈来实现，它是当代大多数程序设计语言实现子程序结构的基础。假定某个调用函数调用了一个被调用函数，再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。

程序员需保证递归函数不会随意改变静态变量和全局变量的值，以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程，并且返回到顶层。

自己调用本身，这样就是递归。那么有人可能会想，这不是死循环吗？的确，如果不小心，很容易造成死循环。因此，在递归函数中，一定要保证递归得以下降为较简单的问题，如果递归不能下降，函数将会形成死循环。

在某些场合，使用递归比使用循环要简单得多。而且有些题目，一看就知道应该使用递归而不是循环来处理。相反，有些问题则不需要使用递归过程来解决。比如，阶乘完全可以采用简单的循环来处理：

程序如此改写后，可以减小计算机系统的堆栈开销，改善程序所使用的空间及运行效率。

4 .结论

递归，在数学和计算机科学中都是一种重要的求解问题的方法。递归程序设计思想是计算机编程思想中分治思想的典型代表。很多看似复杂或者难于理清头绪的问题使用递归方法能以简单易懂的形式一下子得到解决。

但是，凡事有利必有弊，我们需要适当地使用递归函数，切不可盲目滥用。基于递归函数的运行机制，某些能够采用循环的方法直接实现的过程，可以避免使用递归算法，以改善程序的运行效率。

[1] 谭浩强. C++程序设计[M]. 北京：清华大学出版社，2004.

[2] 郑莉. C++语言程序设计[M]. 北京：清华大学出版社，2003.

[3] 黄欣阳，等. 如何用递归方法进行程序设计[J]. 福建电脑，2011，（6）.

[4] 邵利平. 程序语言教学中的递归程序思维培养[J]. 电脑知识与技术，2011，（29）.

Simple Analysis of the Realization of Recursive Function in C++ Language

CHEN Ying-xin, LI Zhu-guo

In this Paper, the concept of Recursive Function is studied combined with daily life. The way to program recursive functions is shown by samples, and its call mechanism is analyzed. The benefit and disadvantage of these functions are concluded, while the principle to use recursive thought properly is also proposed.

Recursion; Function; Programming; C++ Language

TP311.1

A

1008-7427（2012）09-0159-02

2012-05-04