《数据结构C语言版》----第06章ppt课件.ppt

《《数据结构C语言版》----第06章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章递归算法递归的概念递归算法的执行过程递归算法的设计方法递归过程和运行时栈递归算法的效率分析设计举例主要知识点1存在算法调用自己的情况：若一个算法直接的或间接的调用自己本身，则称这个算法是递归算法。（1）问题的定义是递推的阶乘函数的常见定义是：6.1递归的概念2也可定义为：写成函数形式，则为：这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数，称公式（6–3）是阶乘函数的递推定义式。3（2）问题的解法存在自调用一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法。4图6-1折半查找过程56.2递归算法的执行过程

2、例6-1给出按照公式6-3计算阶乘函数的递归算法，并给出n=3时递归算法的执行过程。设计：按照公式6-3计算阶乘函数的递归算法如下：6longintFact(intn){intx;longinty;if(n<0)//n<0时阶乘无定义{printf(“参数错！”);return-1;}if(n==0)return1;else{y=Fact(n-1);//递归调用returnn*y;}}7设计主函数如下voidmain(void){longintfn;fn=Fact(3);}主函数用实参n=3调用了递归算法Fact(3)，而Fact

3、(3)要通过调用Fact(2)、Fact(2)要通过调用Fact(1)、Fact(1)要通过调用Fact(0)来得出计算结果。Fact(3)的递归调用过程如图6-2所示。8图6-2Fact(3)的递归调用执行过程9例6-2给出在有序数组a中查找数据元素x是否存在的递归算法，并给出如图6-1所示实际数据的递归算法的执行过程。递归算法如下：10intBSearch(inta[],intx,intlow,inthigh){intmid;if(low>high)return-1;　　　//查找不成功mid=(low+high)/2;if(

4、x==a[mid])returnmid;//查找成功elseif(xmain(void){inta[]={1,3,4,5,17,18,31,33};intx=17;intbn;bn=BSearch(a,x,0,7);if(bn==-1)printf("x不在数组a中");elseprintf("x在数

5、组a的下标%d中",bn);}12BSearch(a,x,0,7)的递归调用过程如图6-3所示，其中，实箭头表示函数调用，虚箭头表示函数的返回值。图6-3BSearch(a,x,0,7)的递归调用过程13146.3递归算法的设计方法递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。递归算法求解问题的基本思想是：对于一个较为复杂的问题，把原问题分解成若干个相对简单且类同的子问题,这样，原问题就可递推得到解。15适宜于用递归算法求解的问题的充分必要条件是：（1）问题具有某种可借用的类同自身的子问题描述的性质；（2）某一

6、有限步的子问题（也称作本原问题）有直接的解存在。当一个问题存在上述两个基本要素时，该问题的递归算法的设计方法是：（1）把对原问题的求解设计成包含有对子问题求解的形式。（2）设计递归出口。16例6-3设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的描述是：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上，移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。17问题分析：可以用递归方法

7、求解n个盘子的汉诺塔问题。基本思想：1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺塔问题可递归表示为，首先把上边的n-1个盘子从A柱移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再移到C柱。4个盘子汉诺塔问题的递归求解示意图如图6-4所示。18图6-4汉诺塔问题的递归求解示意图19算法设计：首先，盘子的个数n是必须的一个输入参数，对n个盘子,我们可从上至下依次编号为1,2,…,n；其次，输入参数还需有3个柱子的代号,我们令3个柱子的参数名分别为fromPeg，auxPeg和toPeg；最后，汉诺塔问题

8、的求解是一个处理过程，因此算法的输出是n个盘子从柱子fromPeg借助柱子auxPeg移动到柱子toPeg的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息：MoveDiskifromPegXtoPegY这样，汉诺塔问题的递归算法可设计如下：