新编C语言程序设计教程PPT第7章函数

新编C语言程序设计教程清华大学出版社,周二强zeq软件学院计算机科学与工程系配套视频：博客：,第7章函数,7.5.2递归算法示例,递归算法与递归函数（二）,把直接或间接地调用自身的函数称为递归函数。fac(5);函数的递归调用是函数嵌的套调用。函数的递归调用是特殊的函数嵌套调用。,递归函数的两个角度,技术,算法,递归算法解决问题有两个过程：,递推的过程回归的过程,递推的过程,Text,子问题,地,地,原问题与子问题：性质相同规模缩小,回归的过程,递归算法举例,例7-22把用户输入的一行字符逆序输出，如输入abc，则输出cba。分析：解决这个问题可以分三步：第一步得到用户输入的第一个字符（a）；第二步把余下的字符（bc）逆序输出（cb）；第三步输出第一个字符（a即得到cba）。在上面的算法中第二步与原问题性质相同，规模变小，这个算法为递归算法。子问题规模缩小到何种程度才能解决呢？不管输入字符串的长短，最后都有一个回车符，如果字符为回车符时，问题就解决了。,例7-22把用户输入的一行字符逆序输出,递归函数可描述如下：1.得到输入字符中的第一字符2.如果字符为n，则直接返回否则，调用f函数逆序输出剩余的字符再输出第一字符。,例7-22把用户输入的一行字符逆序输出,用户输入abcn，则变量c的值为a,缓冲区中有数据bcn故c的值为b,缓冲区中有数据cn故c的值为c,缓冲区中有数据n故c的值n,递归函数优雅地实现了递归算法,递归函数的关键,转化子问题的求解,递归算法举例,例7-26楼梯有n阶台阶，上楼时一步可以上1阶，也可上2阶，编程计算共有多少种不同的走法。分析：设n阶台阶的走法为f(n)当楼梯只有1阶时，显然仅有1种走法，故f(1)1；楼梯只有2阶时可以有2种走法，一步1阶地走上楼梯或一步2阶直接走上楼梯,故f(2)2。现在是n阶楼梯，共有多少种不同的走法呢？,先考虑上楼梯时第一步如何走？只有两种情况：上1阶和上2阶n阶楼梯的不同走法等于这两种情况下所有不同走法的总和。第一步上1阶时走法有多少种？还有n1阶楼梯需要上。剩余的楼梯有多少种不同走法？性质相同，规模变小！n阶台阶的走法为f(n)，剩余n1阶的楼梯的走法当然有f(n-1)种！第一步上2阶时走法有多少种呢？,例7-26n阶楼梯有几种不同的走法,例7-25n阶楼梯有几种不同的走法,设n阶台阶的走法为f(n)，则f(n)的定义为：1n=1;2n=2;f(n-1)+f(n-2)n2;递归函数f(n)用程序实现为：intupstairs(intn)if(n=1|n=2)returnn;returnupstairs(n-1)+upstairs(n-2);,求4阶楼梯有多少种不同的走法,voidmain()printf(“4阶楼梯有%d种不同的走法n”,upstairs(4);,分析upstairs(4)的运行情况,upstairs(4),程序的输出为,voidmain()printf(“4阶楼梯有%d种不同的走法n”,upstairs(4);,分析upstairs(4)的运行情况,upstairs(3),分析upstairs(4)的运行情况,左边的走法：1-1-1-1，1-1-2中间的走法：1-2-1右边的走法：2-1-1,2-2,总结,递归算法解决问题的思路：把规模较大的问题转化为性质相同规模较小的问题，一直转化下去，因为问题的难易度通常与其规模相关，当问题的规模小到一定程序时就很容易得到解，规模小的问题有解了，再利用这个解得到规模稍大的问题的解，一直回归直到得到原问题的解。C语言中利用递归函数优雅地实现了递归算法。,强调,学习递归函数一方面要会分析递归函数的执行情况另一方面要会用递归算法解决问题,例7-23猴子吃桃。,有若干桃子，一只猴子第一天吃了一半多一个，第二天吃了剩下的一半多一个，每天如此，第十天吃时只有一个桃子了，一共有多少个桃子？（例5-16）f(n)表示第n天原有的桃子。第十天吃时只有一个桃子了，则f(10)=1。求共有多少个桃子，就是求第一天原有多少个桃子，即求f(1)是多少。如果知道f(2)（第二天原有的桃子也是第一天剩下的）就好了，因为有f(1)=(f(2)+1)*2（由等式f(2)=f(1)-(f(1)/2+1)可得），这样求f(1)就变成了求f(2)。猴子吃桃的规律相同，因此函数f(n)可定义如下：,例7-23猴子吃桃。,例7-24,输入一个自然数，若为偶数，则把它除以2；若为奇数，则把它乘以3再加1，经过如此有限次处理，总可以得到自然数1。编程模拟该过程。如输入23时输出23703510653160804020105168421用了16步!设函数f(n)可以完成这个操作，则该函数的定义如下。,例7-24,例7-25,编写一个递归函数isPalin判断字符数组中的字符串是否为回文，是则返回1，不是返回0。,例7-27汉诺塔问题。,古代有一个梵塔，塔内有3个标示为A、B、C的座，A座上有5个大小不等的盘子，大的在下面，小的在上面，如图7-8所示。现要求把5个盘子从A座移动到C座，每次只允许移动一个盘子，在移动过程中可以利用B座，但是3个座上要始终保持大盘在下面，小盘在上面。,例7-27汉诺塔问题。,设A座上有n个盘子。如果n为1时，即A座上只有一个盘子，则把它直