新编C语言程序设计教程第7章函数课件.ppt

1、新编C语言程序设计教程 清华大学出版社周二强周二强 软件学院软件学院 计算机科学与工程系计算机科学与工程系配套视频：配套视频： 博客：博客： 7.5.2 递归算法示例第2页，共32页。递归算法与递归函数（二）把直接或间接地调用自身的函数称为递归函数。把直接或间接地调用自身的函数称为递归函数。fac(5);fac(5);函数的递归调用是函数嵌的套调用。函数的递归调用是函数嵌的套调用。函数的递归调用是特殊的函数嵌套调用。函数的递归调用是特殊的函数嵌套调用。第3页，共32页。递归函数的两个角度第4页，共32页。递归算法解决问题有两个过程：递推的过程回归的过程第5页，共32页。递推的过程有解的有解的T

2、ext子问题子问题地地原问题原问题与子问题：性质相同规模缩小第6页，共32页。回归的过程解解解解解解解第7页，共32页。递归算法举例例例7-22 7-22 把用户输入的一行字符逆序输出，如输入把用户输入的一行字符逆序输出，如输入abcabc，则输出，则输出cbacba。分析：解决这个问题可以分三步：分析：解决这个问题可以分三步：第一步得到用户输入的第一个字符（第一步得到用户输入的第一个字符（a a）；）；第二步把余下的字符（第二步把余下的字符（bcbc）逆序输出（）逆序输出（cbcb）；）；第三步输出第一个字符（第三步输出第一个字符（a a即得到即得到cbacba）。）。在上面的算法中第二步与

3、原问题性质相同，规模变小，这个算法为递归在上面的算法中第二步与原问题性质相同，规模变小，这个算法为递归算法。算法。子问题规模缩小到何种程度才能解决呢？不管输入字符串的长短，最后子问题规模缩小到何种程度才能解决呢？不管输入字符串的长短，最后都有一个回车符，如果字符为回车符时，问题就解决了。都有一个回车符，如果字符为回车符时，问题就解决了。第8页，共32页。例7-22 把用户输入的一行字符逆序输出递归函数可描述如下：递归函数可描述如下：1.1.得到输入字符中的第一字符得到输入字符中的第一字符2.2.如果字符为如果字符为nn，则直接返回，则直接返回 否则，调用否则，调用f f函数逆序输出剩余的字符函

4、数逆序输出剩余的字符 再输出第一字符。再输出第一字符。第9页，共32页。例7-22 把用户输入的一行字符逆序输出第10页，共32页。用户输入abcn，则变量c的值为a缓冲区中有数据bcn故c的值为b缓冲区中有数据cn故c的值为c缓冲区中有数据n故c的值n第11页，共32页。递归函数优雅地实现了递归算法第12页，共32页。递归函数的关键转化转化子问题的求解子问题的求解第13页，共32页。递归算法举例例例7-26 7-26 楼梯有楼梯有n n阶台阶，上楼时一步可以上阶台阶，上楼时一步可以上1 1阶，也可上阶，也可上2 2阶，编程阶，编程计算共有多少种不同的走法。计算共有多少种不同的走法。分析：分析

5、：设设n n阶台阶的走法为阶台阶的走法为f(n)f(n)当楼梯只有当楼梯只有1 1阶时，显然仅有阶时，显然仅有1 1种走法，故种走法，故f(1)f(1)1 1；楼梯只有；楼梯只有2 2阶时可阶时可以有以有2 2种走法，一步种走法，一步1 1阶地走上楼梯或一步阶地走上楼梯或一步2 2阶直接走上楼梯阶直接走上楼梯,故故f(2)f(2)2 2。现在是。现在是n n阶楼梯，共有多少种不同的走法呢？阶楼梯，共有多少种不同的走法呢？第14页，共32页。先考虑上楼梯时第一步如何走？先考虑上楼梯时第一步如何走？只有两种情况：上只有两种情况：上1 1阶和上阶和上2 2阶阶n n阶楼梯的不同走法等于这两种阶楼梯的

6、不同走法等于这两种情况下所有不同走法的总和。情况下所有不同走法的总和。第一步上第一步上1 1阶时走法有多少种？阶时走法有多少种？还有还有n n1 1阶楼梯需要上。阶楼梯需要上。剩余的楼梯有多少种不同走法？剩余的楼梯有多少种不同走法？性质相同，规模变小！性质相同，规模变小！n n阶台阶的走法为阶台阶的走法为f(n)f(n)，剩余，剩余n n1 1阶的楼梯的走法当然有阶的楼梯的走法当然有f(n-1)f(n-1)种！种！第一步上第一步上2 2阶时走法有多少种呢？阶时走法有多少种呢？例7-26 n阶楼梯有几种不同的走法第15页，共32页。例7-25 n阶楼梯有几种不同的走法设设n n阶台阶的走法为阶台

7、阶的走法为f(n)f(n)，则，则f(n)f(n)的定义为：的定义为：1 n=1;1 n=1;2 n=2;2 n=2;f(n-1)+f(n-2)n2;f(n-1)+f(n-2)n2;递归函数递归函数f(n)f(n)用程序实现为：用程序实现为：int upstairs(int n)int upstairs(int n)if(n=1|n=2)return n;if(n=1|n=2)return n;return upstairs(n-1)+upstairs(n-2);return upstairs(n-1)+upstairs(n-2);第16页，共32页。求4阶楼梯有多少种不同的走法void ma

8、in()void main()printf(“4 printf(“4阶楼梯有阶楼梯有%d%d种不同的走法种不同的走法n”,upstairs(4);n”,upstairs(4);第17页，共32页。分析upstairs(4)的运行情况upstairs(4)upstairs(3)upstairs(2)upstairs(2)upstairs(1)第18页，共32页。程序的输出为void main()printf(“4阶楼梯有阶楼梯有%d种不同的走法种不同的走法n”,upstairs(4);第19页，共32页。分析upstairs(4)的运行情况upstairs(4)upstairs(3)upstai

9、rs(2)upstairs(2)upstairs(1)第20页，共32页。分析upstairs(4)的运行情况左边的走法：左边的走法：1-1-1-11-1-1-1，1-1-21-1-2中间的走法：中间的走法：1-2-11-2-1右边的走法：右边的走法：2-1-1,2-22-1-1,2-2upstairs(4)upstairs(3)upstairs(2)upstairs(2)upstairs(1)第21页，共32页。总结递归算法解决问题的思路：递归算法解决问题的思路：把规模较大的问题转化为性质相同规模较小的问题，一直转化下去，把规模较大的问题转化为性质相同规模较小的问题，一直转化下去，因为问题的

10、难易度通常与其规模相关，当问题的规模小到一定程序时因为问题的难易度通常与其规模相关，当问题的规模小到一定程序时就很容易得到解，规模小的问题有解了，再利用这个解得到规模稍大就很容易得到解，规模小的问题有解了，再利用这个解得到规模稍大的问题的解，一直回归直到得到原问题的解。的问题的解，一直回归直到得到原问题的解。C C语言中利用递归函数优雅地实现了递归算法。语言中利用递归函数优雅地实现了递归算法。第22页，共32页。强调学习递归函数学习递归函数一方面要会分析递归函数的执行情况一方面要会分析递归函数的执行情况另一方面要会用递归算法解决问题另一方面要会用递归算法解决问题第23页，共32页。例7-23猴

11、子吃桃。有若干桃子，一只猴子第一天吃了一半多一个，第二天吃了剩下的一有若干桃子，一只猴子第一天吃了一半多一个，第二天吃了剩下的一半多一个，每天如此，第十天吃时只有一个桃子了，一共有多少个桃子半多一个，每天如此，第十天吃时只有一个桃子了，一共有多少个桃子？（例？（例5-165-16）f(n)f(n)表示第表示第n n天原有的桃子。第十天吃时只有一个桃子了，则天原有的桃子。第十天吃时只有一个桃子了，则f(10)=1f(10)=1。求共有多少个桃子，就是求第一天原有多少个桃子，即求。求共有多少个桃子，就是求第一天原有多少个桃子，即求f(1)f(1)是多少是多少。如果知道。如果知道f(2)f(2)（第

12、二天原有的桃子也是第一天剩下的）就好了，因为（第二天原有的桃子也是第一天剩下的）就好了，因为有有f(1)=(f(2)+1)f(1)=(f(2)+1)*2 2（由等式（由等式f(2)=f(1)-(f(1)/2+1)f(2)=f(1)-(f(1)/2+1)可得），这样求可得），这样求f(1)f(1)就变成了求就变成了求f(2)f(2)。猴子吃桃的规律相同，因此函数。猴子吃桃的规律相同，因此函数f(n)f(n)可定义如下可定义如下：第24页，共32页。例7-23猴子吃桃。第25页，共32页。例7-24输入一个自然数，若为偶数，则把它除以输入一个自然数，若为偶数，则把它除以2 2；若为奇数，则把它乘；

13、若为奇数，则把它乘以以3 3再加再加1 1，经过如此有限次处理，总可以得到自然数，经过如此有限次处理，总可以得到自然数1 1。编程模拟该。编程模拟该过程。如输入过程。如输入2323时输出时输出23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 123 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1用了用了1616步步!设函数设函数f(n)f(n)可以完成这个操作，则该函数的定义如下。可以完成这个操作，则该函数的定义如下。第26页，共32页。例7-24第27页，共32页。例7-25编写一个递归函数编写一个递归函数isPalin

14、isPalin判断字符数组中的字符串是否为回文，判断字符数组中的字符串是否为回文，是则返回是则返回1 1，不是返回，不是返回0 0。第28页，共32页。例7-27 汉诺塔问题。古代有一个梵塔，塔内有古代有一个梵塔，塔内有3 3个标示为个标示为A A、B B、C C的座，的座，A A座上有座上有5 5个大小个大小不等的盘子，大的在下面，小的在上面，如图不等的盘子，大的在下面，小的在上面，如图7-87-8所示。现要求把所示。现要求把5 5个个盘子从盘子从A A座移动到座移动到C C座，每次只允许移动一个盘子，在移动过程中可以座，每次只允许移动一个盘子，在移动过程中可以利用利用B B座，但是座，但是

15、3 3个座上要始终保持大盘在下面，小盘在上面。个座上要始终保持大盘在下面，小盘在上面。第29页，共32页。例7-27 汉诺塔问题。设设A A座上有座上有n n个盘子。个盘子。如果如果n n为为1 1时，即时，即A A座上只有一个盘子，则把它直接移到座上只有一个盘子，则把它直接移到C C座上座上否则，用下面三步完成任务：否则，用下面三步完成任务：第一步，把第一步，把A A座上的座上的n-1n-1个盘子先利用个盘子先利用C C座移动到座移动到B B座上。座上。第二步，把第二步，把A A座上仅有的第座上仅有的第n n个盘子移动到个盘子移动到C C座上。座上。第三步，把第三步，把B B座上的座上的n-1n-1个盘子利用个盘子利用A A座移动到座移动到C C座上。座上。第30页，共32页。例7-27 汉诺塔问题。第31页，共32页。return第32页，共32页。