程序设计基础11_2_递归

《程序设计基础11_2_递归》由会员分享，可在线阅读，更多相关《程序设计基础11_2_递归（85页珍藏版）》请在金锄头文库上搜索。

1、第11章 递推与递归,开 始,1,主要内容,递推 递归 递归与分治 递归与回溯,2,递归的概念,先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之为递归。 递归的定义： 在一个函数的定义中又直接或间接地调用该函数本身，称为递归。递归是一种非常有用的程序设计方法。,3,递归算法的基本思想 把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，

2、从而得到原来问题的解。 递归算法的特点 用递归算法编写的程序结构清晰，具有很好的可读性；但程序的效率比较低。,4,递归的应用场合,当问题具备以下特点之一时，往往采用递归算法来解决： 问题本身是递归定义的，如Fibonacci数列问题 ； 问题涉及到的数据结构是递归定义的，如树、图等 ； 问题的解决方法是递归形式的，如汉诺塔问题 ；,5,例 输出Fibonacii数列的第n项 #include int fib(int n) if (n=1) return 1; else return fib(n-1)+fib(n-2); void main( ) int n; scanf(“%d“, ,6,上面

3、是斐波那契数列的递归调用树，可以看出同一个fib(i)被调用多次，因此递归算法编写的程序效率比较低。,Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(4),Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(1),Fib(2),Fib(3),Fib(5),7,递归设计的要件,(1) 在函数中必须有直接或间接调用自身的语句； (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口（或递归边界）。,8,编写递归算法时，首先要对问题的以下三个方面进行分析： 决定问题规模的参数。 需要用递归算法解决的问题，其规模通常都是比较大的，在

4、问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。 问题的边界条件及边界值。 在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。 解决问题的通式。 把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。把这些步骤或等式确定下来。,9,递归设计实例,例10.5 汉诺（Hanoi）塔问题 （1）相传在古代印度的一个寺庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64只一个比一个小的盘子从柱子A上借助柱子B移到柱子C上去。 （2）移动过程恪守下述规则：每次只允许移动一只盘子，且大盘子不得落在小盘子上面。

5、（3）有人觉得这很简单，但真的动手才发现，如以每秒移动一只盘子，按照上述规则将64只盘子从柱子A移到柱子C上，所需时间也是很多年。,10,11,汉诺塔的目标是将初始位置的n个盘子从初始位置A借助于中间位置B移动到目标位置C，可以按照以下三个步骤来执行： 第一步：将初始位置A上面的n-1个盘子借助目标位置C，移动到中间位置B暂时存放； 第二步：将初始位置A最下面的大盘子直接移动到目标位置C； 第三步：将中间位置B暂存的n-1个盘子借助初始位置A移动到目标位置C,12,Hanoi塔问题,#include int step=1; / 整型全局变量, 预置1, 步数 void move(int,cha

6、r,char,char); void main() int n; printf(“请输入盘数 n=“); scanf(“%d“, ,13,void move(int m,char p,char q,char r) if (m=1) / 如果1个盘子，则为直接可解结点, printf(“n%d move %d# from %c to %c“,step,m,p,r); step+; / 步数加1 else move(m-1,p,r,q); / 递归调用move printf(“n%d move %d# from %c to %c“,step,m,p,r); step+; / 步数加1 move(m

7、-1,q,p,r); / 递归调用move ,14,Hanoi塔问题的特点,N个盘子的从A到B的移动可以分成三步： N-1个盘子从A到B的移动； 1个盘子从A到C的移动 N-1个盘子从B到C的移动； 这三步对应的问题具备以下共性： 仍然是盘子的移动问题； 是规模更小的盘子的移动问题； 所以，可以递归求解这些问题。,15,再来看一个问题， 看看与前者有没有共同之处？,16,例11.6：青蛙过河 一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。规定初始时这队青蛙只能趴在左岸的石头

8、L上，当然是按号排一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有S个石柱，有 y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求按号排一个落一个，大的在下，小的在上。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样 ，允许多个青蛙按号排一个落一个，小的在上，大的在下。当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已知溪中有S根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？,17,解题思路： 1、定义函数： Jump(S,y) 最多可跳过河的青蛙数 其中

9、： S为河中柱子数，y为荷叶数 2、先看简单情况，河中无柱子：S=0，即Jump(0,y) 。,18,解题思路： 当y=1时，河中有一片荷叶，起始时L上有两只青蛙，1#在2#上面。 第一步：1# 跳到荷叶上； 第二步：2# 从L直接跳至R上； 第三步：1# 再从荷叶跳至R上。 因此：Jump(0,1)=2；,左岸L,右岸R,荷叶,19,当y=2时河中有两片荷叶时，起始时：1#，2#，3# 3只青蛙落在L上， 第一步：1# 从L跳至叶 1上， 第二步：2# 从L跳至叶 2上， 第三步：3# 从L直接跳至R上， 第四步：2# 从叶2跳至R上， 第五步：1# 从叶1跳至R上 说明：河中有两片荷叶时，

10、可以过3只青蛙：Jump(0,2)=3；,左岸L,右岸R,荷叶2,荷叶1,20,那么，请思考： Jump(0,3)=? Jump(0,4)=? Jump(0,y)=? 采用归纳法：Jump(0,y)=y+1 在河中没有石柱的情况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数+1。,21,1# 青蛙从 L Y； 2# 青蛙从 L S； 1# 青蛙从 Y S； 3# 青蛙从 L Y； 4# 青蛙从 L R； 3# 青蛙从 Y R；,左岸L,右岸R,荷叶Y,石柱S,1# 青蛙从 S Y； 2# 青蛙从 S R； 1# 青蛙从 Y R； 可以看出，Jump(1,1)=2*Jump(0,1)=2*2=4,

11、3、再看Jump(S, y): 先看一个最简单情况：S=1、y=1时，,22,参照汉诺塔问题，可将借助一个荷叶、一个石柱的青蛙跳跃问题分成五个步骤： 第一步：借助荷叶将左岸上面的若干青蛙（这里是1#与2#两只）跳到石柱上暂存； 第二部：左岸的下一只青蛙（这里是3#）跳到荷叶上； 第三步：左岸的再下一只青蛙（这里是4#）完成到右岸的直接跳跃； 第四步：荷叶暂存的青蛙完成到右岸的跳跃； 第五步：石柱上暂存的青蛙借助荷叶完成到右岸的跳跃；,23,第一、五两步实际上完成的就是青蛙借助一个荷叶跳跃的过程，并且这两步的对象是同一批青蛙，所以个数是Jump(0,1)。 第二、三、四步实际上完成的也是青蛙借助

12、一个荷叶跳跃的过程，所以个数也是Jump(0,1)。 所以，Jump(1,1)与Jump(0,1)是相关的，即： Jump(1,1)=2*Jump(0,1)；,24,按照这样的思路，借助s个石柱、y个荷叶的青蛙跳跃过程也可以类似的归纳出来，这个实现步骤可以分成七个步骤： 第一步：借助所有荷叶以及其余石柱将左岸上面的若干青蛙跳到第一个石柱上暂存； 第二步：左岸的余下的青蛙借助其它可用的石柱以及所有荷叶跳到其它石柱上； 第三步：左岸的再余下的青蛙跳到所有荷叶上 第四步：左岸的再下一只青蛙完成到右岸的直接跳跃； 第五步：荷叶暂存的青蛙完成到右岸的跳跃； 第六步：除了第一个外其余石柱上暂存的青蛙完成到

13、右岸的跳跃； 第七步：第一个石柱上暂存的青蛙借助其余石柱以及所有荷叶完成到右岸的跳跃,25,类似的，如果以上的石柱在跳跃过程中可以看成右岸或左岸的话，这里的七个步骤也可以简化成两个阶段： 第一、七两步实际上是青蛙借助s-1个石柱以及y个荷叶，完成从左岸到第一个石柱，再到右岸的跳跃的过程，而这两步的对象是同一批青蛙，所以个数是Jump(s-1,y)。 第二步到第六步完成的是左岸的青蛙借助剩余的n-1个石柱以及所有y个荷叶跳跃到右岸的过程，所以个数也是Jump(s-1,y)。 所以，Jump(S, y)与Jump(s-1,y)是相关的，即： Jump(s,y)=2*Jump(s-1,y)； 当石柱

14、数目为0是不需要递归的，此时跳跃的青蛙数目为荷叶数目+1，即递归的结束条件为： Jump(0,y)=y+1;,26,#include int Jump(int, int); /声明有被调用函数 void main() int s,y,sum; /整型变量,s为河中石柱数,y为荷叶数 printf(“请输入石柱数s=“ ); /提示信息 scanf(“%d“, ,27,int Jump(int r,int z) /整型自定义函数,r,z为形参 int k; if (r=0) /如果r为0,则不再递归, k=z+1; else /如果不为0,则递归调用Jump(r-1,z) k=2*Jump(r-

15、1,z); return(k); ,28,【例11.7】 快速排序,选择排序、冒泡排序的排序思路比较简单，但是排序效率较低，不能满足需求（比如在OJ或比赛题目中） 有没有一些效率更高的排序方法呢？ 快速排序是利用分治递归技术实现的一种高效的方法。 何为分治递归? 分治法简而言之就是“分而治之”，亦即把一个复杂的问题分成两个或更多的子问题，再把子问题分成更小的子问题直到最后分解成的子问题可以直接求解，原问题的解即子问题的解的合并。,29,将要求解的较大规模的问题分割成k个更小规模的子问题。,分治法思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,30,分治法思想,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,n,T(n),=,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,31,分治法思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,32,分治法思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，