c语言高级编程[1]

《c语言高级编程[1]》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、·287·C语言高级编程技术C语言高级编程技术8.1递归程序设计8.1.1递归与递归程序设计递归技术在算法和程序设计中是一种十分有用的技术，C语言提供了支持递归定义的机制和手段。递归有直接递归和间接递归两种。在一个函数的定义中出现了对自身的调用，称之为直接递归；一个函数f的定义中包含了对函数g的调用，而g的实现过程又调用了f，即函数调用形成了一个环状调用链,这种方式称之为间接递归。页：237例8.1编写一个递归函数，求n的阶乘值n！。若用fact(n)表示n的阶乘值，根据阶乘的数学定义可知：显然,当n>0时，fact(n)是建立在fact(n-1)的基础上。由于求解fact(n-1)

2、的过程与求解fact(n)的过程完全相同，只是具体实参不同，因而在进行程序设计时，不必再仔细考虑fact(n-1)的具体实现，只需借助递归机制进行自身调用即可。于是求n的阶乘值fact(n)的具体实现为：longfact(intn){longm;if(n==0)return(1);else{m=n*fact(n-1);return(m);}}例8.2编写一个递归函数，求Fibonacci数列第n项的值。若用Fibona(n)表示Fibonacci数列第n项的值，根据Fibonacci数列的计算公式：可知当n>2时，Fibonacci数列第n项的值等于第n-1项的值与第n-2项的值相加

3、之和，而Fibonacci数列第n-1项和第n-2项值的求解又分别取决于它们各自前两项之和。总之，Fibona(n-1)和Fibona(n-2)的求解过程与Fibona(n)的求解过程相同，只是具体实参不同。利用以上这种性质，我们在进行程序设计时便可以使用递归技术，Fibona(n-1)和Fibona(n-2)·287·C语言高级编程技术的求解只需调用函数Fibona自身加以实现即可。具体实现为：intFibona(intn){intm;if(n==1

4、

5、n==2)return(1);else{m=Fibona(n-1)+Fibona(n-2);return(m);}}从上面两个实例

6、可以看出，要使用递归技术进行程序设计，首先必须将要求解的问题分解成若干子问题，这些子问题的结构与原问题的结构相同，但规模较原问题小。由于子问题与原问题结构相同，因而它们的求解过程相同，在进行程序设计时，不必再仔细考虑子问题的求解，只需借助递归机制进行函数自身调用加以实现，然后利用所得到的子问题的解组合成原问题的解即可；而递归程序在执行过程中，通过不断修改参数进行自身调用，将子问题分解成更小的子问题进行求解，直到最终分解成的子问题可以直接求解为止。综上所述，递归程序设计具有以下两个特点：（1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到满足时，递归执行过程便终止。有

7、些问题的递归程序可能存在几个递归出口；（2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题，子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。8.1.2递归程序执行过程的分析递归程序的执行过程分为递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如例8.2中，求解Fibona(n)，把它推到求解Fibona(n-1)和Fibona(n-2)。即是说，为计算Fibona(n)，必须先计算Fibona(

8、n-1)和Fibona(n-2)，而计算Fibona(n-1)和Fibona(n-2)，又必须先计算Fibona(n-3)和Fibona(n-4)。依次类推，直至计算Fibona(1)和Fibona(2)，分别能立即得到结果1和1。在递推阶段，必须要有终止递归的情况。例如在函数Fibona中，当n为1和2的情况。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到Fibona(1)和Fibona(2)后，返回得到Fibona(3)的结果，……，在得到了Fibona(n-1)和Fibona(n-2)的结果后，返回得到Fibona(n)的结果。在编写递归函数时要

9、注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数Fibona(n)应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计