数据结构2_第6章_1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,六,章 递归,算法,掌握：,递归的概念：什么是递归，种类，及递归求解方法,递归过程的机制与利用递归工作栈实现递归的方法,利用递归解决问题的分治法和回溯法,了解：,迷宫问题的递归思路及利用栈实现的非递归解法,一、递归的概念,定义：若一个对象部分地包含它自己，或用它自己给自己定义，则,称这个对象是递归的；而且一个过程直接地或间接地调用自,己，则称这个过程是递归的过程。,应用：,（1）用于某些概念的定义：,阶乘：,if(n0)n!=n(n-1)!,if(n=0)n!=1,单链表结点：,typedef struct node,datatype data,struct node*Link;,slnode,二叉树：二叉树是数据元素的有穷集合，它或者为空集（空 二叉树），,或者由一个根元素和其下的两棵互不相交的二叉树（左子树,和右子树）构成。,递归算法的一般形式：,void p(,参数表),if （,递归结束条件）可直接求解步骤；-基本项,else p（,较小的参数）；-归纳项,递归算法的优点：易编程、可读性好、易检验,可用归纳思维方法来理解和检验递归算法，但有一个基本条件和两个步骤：,基本条件：规格说明必须严格、精确地规定算法的功能、入/出口信息、对外层量或全局量的影响,步骤一：归纳基始验证算法对于最简单情况（递归出口）的正确性,步骤二：由归纳假设进行归纳假设算法中的递归调用 能正确实现规格说明之规定，然后验证整个算法能否实现规格说明之规定,例：求,n!=,long Factorial(long n),if(n=0)return 1;,else return n*Factorial(n-1);,1，,n=0,n*(n-1)！,n0,Factorial(4);,例5-3：有5人坐在一起，问第5号人多少岁？他说比第4号人大2岁，问第4号人他又说比第3号人大2岁，依次下去，问到最后一个人，他说他已10岁，请问第5号人多大？,10,n=1,f(n)=,f(n-1)+2 n1,int age(int n),int c;,if(n=1),return 10;,else,return age(n-1)+2;,二分查询,例：在,n,个以排好序（设为从小到大）的数据中（数或字符串）中，查询某一个数据。如果找到了，就指出其在,n,个数中的位置；否则给出无该数据的信息，如给出“1”。,（1）问题分析：,当问题的规模较大时，可以将问题分为同类型的规模较小的问题，第归的进行求解。,采用二分法求解本问题的基本思路是：,设数列为,a1,a2,an，,被查找的数为,x，,则查找首先对,a,m,(m=(n+1)/2),进行，于是得到如下三种情形：,若,x a,m,，,则,x,可能在区间,a,m1,a,n,；,若,xa,m,，,那么就递归调用,binsrch(m+1,r,x)，,否则如果,x1,例,Hanoi,问题,void move(char,getone,char,putone,),printf,(%c-%cn,getone,putone,);,void,hanoi,(,int,n,char one,char two,char three),if(n=1)move(one,three);,else,hanoi,(n-1,one,three,two);,move(one,three);,hanoi,(n-1,two,one,three);,main(),int,m;,printf,(Input the number of disks:);,scanf,(%d,printf,(The steps to moving%3d disks:n,m);,hanoi,(m,A,B,C);,A,B,C,运行结果：,只有一个盘子的情况：(最简1步),Input the number of disks:1,The step to moving 1 disks,A-C,有二个盘子的情况：(最简3步),Input the number of disks:2,The step to moving 2 disks,A-B,A-C,B-C,有三个盘子的情况：(最简7步),Input the number of disks:3,The step to moving 3 disks,A-C B-A,A-B B-C,C-B A-C,A-C,6.4 递归过程与运行时栈,调用,返回,调用点,Pn,Pn,-,1,Pn,-,2,P,1,1,为了保证递归调用的正确性，需要保存调用点的现场（返回地,址、局部变量、被调用函数的参数等），以便正确地返回，并且按,先进后出的原则来管理这些信息。在高级语言（编译程序）中，是,通过利用“递归工作栈”来实现递归调用的。,f(n)f(n-1)f(n-2)f(1)f(0),调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场,计算 4!递归过程图示：,下图中,Pi,代表现场信息，栈元素由现场信息和参数构成,f(4)=4*f(3)f(3)=3*f(2)f(2)=2*f(1)f(1)=1*f(0)f(0)=1,Push(e4)Push(e3)Push(e2)Push(e1),f(4)=4*f(3)f(3)=3*f(2)f(2)=2*f(1),f(1)=1*f(0),一般来说，递归方法的执行效率较低，但编程效率较高，因此,常用来构建快速原型。另外递归结构一般可以转化成循环结构（有,时需要栈操作的配合）。试实现上述阶乘计算的转化（要求用栈）。,P,1,1,P,2,2,P,3,3,P,4,4,P,2,2,P,3,3,P,4,4,P,3,3,P,4,4,Pop(e1),Pop(e2),Pop(e3),Pop(e4),P,4,4,6.5 递归算法的效率分析,long fib(int n),if(n=0|n=1)return n,else return fib(n-1)+fib(n-2);,一般从递归过程改为非递归过程的方法是先根据递归算法,画出程序流程图，然后,建立循环结构,。,long Fib(long n),if (n=1)return n;,f0=0,f1=1;,for(i=2;i=n;i+),f2=f1+f0;,f0=f1;,f1=f2;,return f2;,Fib(6)n=6,0、1、,3、,5、,8,2、,1、,6.7 设计举例,例 6-5 :,void display(int n),int i;,for(i=1;i0),display(n-1),;,例6-6:,int comm(int n,int k),if(nn)return 0;,if(k=0)return 1;,if(n=k)return 1;,return comm(n-1,k-1)+comm(n-1,k);,例6-7:,int gcd(int n,int m),if(n0|mn)return gcd(m,n);,else return gcd(m,n%m);,