C语言函数递归调用-C语言程序设计基础（第3版）

2023-11-20 理论教育版权反馈

【摘要】：一个函数直接或间接地调用自己，称为函数的递归调用。所以函数递归调用的实现必须依靠系统提供一个特殊部件（堆栈）存放未完成的操作，以保证当递归调用结束回溯时不会丢失任何应该执行而没有执行的操作。为了理解函数递归调用的特性，参照例5.9的程序讨论函数递归调用的执行过程，为了讨论方便为程序加上行号。函数递归调用示例。

一个函数直接或间接地调用自己，称为函数的递归调用。函数的递归调用可以看成是一种特殊的函数嵌套调用，它与一般嵌套调用相比较有两个不同的特点：一是递归调用中每次嵌套调用的函数都是该函数本身；二是递归调用不会无限制进行下去，即这种特殊的自己对自己的嵌套调用总会在某种条件下结束。

递归调用在执行时，每一次都意味着本次的函数体并没有执行完毕。所以函数递归调用的实现必须依靠系统提供一个特殊部件（堆栈）存放未完成的操作，以保证当递归调用结束回溯时不会丢失任何应该执行而没有执行的操作。计算机系统的堆栈是一段先进后出（FILO）的存储区域，系统在递归调用时将在递归过程中应该执行而未执行的操作依次从栈底开始存放，当递归结束回溯时再依存放时相反的顺序将它们从堆栈中取出来执行，在压栈和出栈操作中，系统使用堆栈指针指示出应该存入和取出数据的位置。为了理解函数递归调用的特性，参照例5.9的程序讨论函数递归调用的执行过程，为了讨论方便为程序加上行号。

【例5.9】　函数递归调用示例（使用递归调的方法反向输出字符串）。

上面程序执行时，若输入数据为字符串：abc＃，则函数reverse的第一次调用时，在程序的第14行读入字符'a'到字符变量ch中，由于ch＝＝'＃'的条件不满足，所以程序应该执行由18～21行构成的复合语句。但在执行由18～21行构成的复合语句时，第19行程序要执行递归调用语句reverse（）；，因而第20行所示的C语句putchar（ch）；就是在该次函数调用过程中应该执行而没有执行的语句，系统将该语句相关的代码压入堆栈保存起来，如图5.8（b）所示，其中的top表示堆栈指针（下同）。

在函数reverse第二次被调用时（注意此时第一次函数调用并未结束），读入字符数据'b'到字符变量ch中，同样由于ch＝＝'＃'的条件不满足，程序应该执行由18～21行构成的复合语句。在第19行要执行递归调用语句reverse（）；，因而第20行所示的C语句putchar（ch）；仍然是应该执行而没有执行的语句，系统将执行该语句的代码压入堆栈保存起来，如图5.8（c）所示。同样在函数reverse第三次被调用时，由于ch＝＝'＃'的条件不满足仍然会执行上面相似的过程，执行情况如图5.8（d）所示。

图5.8　递归调用时系统堆栈数据的变化示意图

当第四次调用函数reverse时，读入字符变量ch的字符为'＃'，此时第15行中的条件ch＝＝'＃'满足，程序执行第16行输出字符数据'＃'。输入字符数据'＃'后，如果静态的看待上面显示的例5.9程序源代码，程序执行应该结束了（注意此时最容易出现错误）。但注意函数reverse的第一次、第二次和第三次调用均未完成，所以程序应该将保存在堆栈中应该执行而未执行的程序代码取出执行。由于堆栈先进后出的特性，所以取出并执行堆栈中代码的顺序与其压入堆栈的顺序相反，在例5.9中首先取出并执行的是函数reverse第三次调用时压入的代码，然后是第二次的代码，最后是第一次的代码，这种回溯的过程一直到取出堆栈中压入的所有代码为止，回溯过程中堆栈的变化情况如图5.8（e）至图5.8（g）所示。所以程序执行时输入数据为字符串：abc＃，则输出数据为字符串：＃cba。

在对例5.9程序的分析中，由于分析了系统堆栈的行为，过程显得比较复杂。但在对递归函数调用进行理解或者在阅读分析含有递归调用函数的C程序时，没有必要过分地追求系统堆栈变化的细节，只要掌握在函数递归的过程中需要将应该执行而未执行的程序代码依次保留下来，当递归结束程序回溯时将保留下来的程序代码用相反的次序依次执行一遍即可。

【例5.10】　编写程序使用递归方式求n！。

图5.9　函数递归调用过程示意图

上面程序运行时首先输入欲求阶乘的整数（本例中以整数5为例），如图5.9所示，程序在运行时将求fac（5）分解为求5*fac（4）、将求fac（4）分解为求4*fac（3）、将求fac（3）分解为求3*fac（2）、将求fac（2）分解为求2*fac（1）、得到fac（1）等于1，然后程序进入递归回溯过程，由fac（1）等于1求得fac（2）等于2、由fac（2）等于2求得fac（3）等于6、由fac（3）等于6求得fac（4）等于24、由fac（4）等于24求得fac（5）等于120，函数递归调用结束。

递归函数的调用，使得程序的执行常常有非常复杂的流程，但在实际设计递归函数时，我们可以忽略系统的具体执行过程，将重点放在分析递归公式和递归终止条件上面，只要算法和递推公式正确，结论一定是正确的，不必陷入分析执行的复杂流程中。

递归的实质是一种简化复杂问题求解的方法，它将问题逐步简化直至趋于已知条件。在简化的过程中必须保证问题的性质不发生变化，即在简化的过程中必须保证两点：一是问题简化后具有同样的形式；二是问题简化后必须趋于比原问题简单一些。具体使用递归技术时，必须能够将问题简化分解为递归方程（问题的形式）和递归结束条件（最简单的解）两个部分。如例5.10求n的阶乘问题，分解出的递归方程为：n*（n-1）！；递归结束条件是：当n＜＝1时，阶乘值为1。

在程序结构上，总是用分支结构来描述递归过程，递归函数的一般结构如下：

if递归结束条件成立

return已知结果；

else

将问题转化为同性质的较简单子问题；(www.chuimin.cn)

以递归方式求解子问题（递归方程）；

【例5.11】　汉诺塔（Tower of Hanoi）问题。有A、B、C三根杆，最左边杆上自下而上、由大到小顺序呈塔形串有64个金盘。现要把左边A杆上的金盘借助C杆全部移到中间B杆上，条件是一次只能移动一个盘，且任何时候都不允许大盘压在小盘的上面。

问题分析：通过计算可以得出，64个盘的移动次数为：264-1＝18，466，744，073，709，511，615次。采用递归方法求解该问题时，可以将问题movetower（n，one，three，two）分解为以下3个子任务：

①以B杆过渡，将上面的1到n-1号盘从A移动C，记为：

movetower（n-1，one，three，two）；

②将A杆的第n号盘移动到B杆；

③以A杆过渡，将1到n-1号盘从C移动B，记为：