电子教案C 语言案例教程第五章6

1、第六节递归法 本节任务 学会用递归法解决不太复杂的问题学习要点 掌握递归法的一般步骤和注意事项【引例】5_6_1 寄信问题。写好了N封不同的信，有X个信箱可投寄。现在小猴去寄信，小猴不识字，随机将信投入信箱。问N封信投放进各个信箱的可能情况有多少种？想一想：这个问题可以这样考虑：第一个封信，可以选择投进的信箱有X个；这时候事情没做完，要投寄第二封信直到投完第N封信。 显然，最后共有XN种情况。现在我们感兴趣的是如何求XN（X0），一般地可以求N个X的连乘积。现在我们从更基础的情况分析，当N=0，XN=1；当N=1，XN=X；当N=K-1，XN=X K-1X。其实这是得到N个X的连乘积这个结论的

2、推导过程。我们将它写成公式： 1 （N=0）S = X （N=1） X N-1X （N1）现在我们按照这个新公式求X的N次幂，它的过程与递推法有类似之处，只不过是先从最后往前推，到最前得到初值，再利用初值反推到最后，使问题求解。 定义将Nn时不能得出解的问题，设法转化为求n1、n2解的问题（入栈），一直到N0或1的情况，因为初始情况的解可以给出或方便得到，然后再层层反推得到N2、3、n时的解（出栈），由此得到最终结果。这种算法，称递归算法。 用递归法编写本例的C源程序如下：/* 5_6L1.C chengmi.c */#includestdio.h long chengmi(int x,int

3、 n); main() int x,n0; printf(enter x,n=); scanf(%d %d,&x,&n0); printf(%d%d=%dnr,x,n,chengmi(x,n0); long chengmi(int x,int n) long ji; if(x=1) ji=x; /* 实现递归停止的语句 */ else if(n=0) ji=1; else ji=x*chengmi(x,n-1); /* 使n逐次递减直到n=1,然后恢复现场用X N-1X反推出XN */ return(ji); 例5_6_2 用递归法求122232 N 2分析：求上述数列的和，其算法是递归的，其

4、实我们可以根据它的递归算法，改成定义是递归的，上述累加和我们可以认为是如下完成的：设Sn 为前n项之和，Sn-1为前n-1项之和。 () Sn Sn-1 +n2 ()用递归法很简单，把该定义写成一个子程序，主程序直接调用子程序和打印输出即可。用递归法编写本例的C源程序如下： /* 5_6L2.C */ #includestdio.h long sum(int n); main() int n0; printf(enter n=); scanf(%d,&n0); printf(S=%dnr,sum(n0); long sum(int n) long ji; if(n=1) ji=1; /* 使递

5、归停止的语句 */ else ji=n*n+sum(n-1); /* 递归求平方和的语句 */ return(ji); 递归是电子计算机的一种极其重要的算法，所以所有的编程语言都非常重视递归。递归，是一种重要的计算现象，也是一种较抽象的思维方式，它的最重要特点是自己调用自己。递归有两个方法，一种是直接递归；如子程序里有调用子程序的语句，则此递归是直接递归，另一种方法是间接递归；如子程序去调用另一个子程序，子程序又调用子程序。则这种递归方法叫间接递归。这两种方法中，大部份可见的程序是用第一种。如果按递归类型来分，递归可分成定义是递归的（如例5_6_1）；算法是递归的（如例5_6_2）；数据结构是

6、递归的。第种本质上就是第一种，因为它其实就是数据的结构类型在定义时，使用了递归的方法定义，因此处理这类数据时用递归来处理就显得极为方便。如“树”就是如此。其实，递归并不神秘。它仅仅起到的是保存断点现场的作用，而在一些复杂问题中，它又可以大大简化程序。递归符合人们实际思维习惯。 小结 递归法实现的关键 递归算法关键是递归子程序的设计。首先应设计好递归结束的条件，不然的话你的递归程序将会运行到系统崩溃为止。然后按照允许递归的条件，设计好什么条件下自己调用自己的语句。 最后按需要设计好返回值的表达式，让递归子程序将返回值带出。 作业与练习：（用递归法求以下问题）1求阶乘 n! =1234n。2裴波那契