递归程序的设计优秀PPT.ppt

《递归程序的设计优秀PPT.ppt》由会员分享，可在线阅读，更多相关《递归程序的设计优秀PPT.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递归程序的设计第一页，本课件共有21页栈的应用举例栈的应用举例栈的应用举例栈的应用举例递归递归递归递归1 递归的定义递归的定义子程序（或函数）直接调用自己或通过一系列调用语子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种句间接调用自己，是一种描述问题描述问题和和解决问题解决问题的基本的基本方法。方法。2 递归的基本思想递归的基本思想问题分解：问题分解：把一个不能或不好解决的大问题转化为把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解成更小的小问题，直至每个小问题都

2、可以直接解决。决。第二页，本课件共有21页3 递归的要素递归的要素 递归边界条件：递归边界条件：确定递归到何时终止，确定递归到何时终止，也称为递也称为递归出口；归出口；递归模式：大问题是如何分解为小问题的，也称递归模式：大问题是如何分解为小问题的，也称为递归体。为递归体。栈的应用举例栈的应用举例栈的应用举例栈的应用举例递归递归递归递归第三页，本课件共有21页例例1 1 阶乘函数阶乘函数递归算法递归算法int fact (int n)if(n=0)return 1;else return n*fact(n-1);-*=时时当当时时当当 )!1(1!n1n1nnn栈的应用举例栈的应用举例栈的应用举

3、例栈的应用举例递归递归递归递归第四页，本课件共有21页求解阶乘求解阶乘 n!n!的过程的过程计算计算 fact(4)计算计算 4*fact(3)计算计算 3*fact(2)计算计算 2*fact(1)计算计算 fact(1)递递归归调调用用回回回回归归归归求求求求值值值值返回返回 24返回返回 6返回返回 2返回返回1栈的应用举例栈的应用举例栈的应用举例栈的应用举例递归递归递归递归第五页，本课件共有21页递归过程与递归工作栈递归过程与递归工作栈递归过程在实现时，需要自己调用自己。递归过程在实现时，需要自己调用自己。层层向下递归，返回次序正好相反：层层向下递归，返回次序正好相反：递归调用递归调用

4、 n!(n-1)!(n-2)!1!=1 返回次序返回次序栈的应用举例栈的应用举例栈的应用举例栈的应用举例递归递归递归递归第六页，本课件共有21页递归函数的内部执行过程递归函数的内部执行过程每一次递归调用时，需要为过程中使用的参每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。记录，按后进先出的栈组织。局部变量局部变量返回地址返回地址值值 参参活动活动记录记录框架框架递归递归工作记录工作记录 运行开始时，首先为递归调用建立一个工作栈，其结运行开始时

5、，首先为递归调用建立一个工作栈，其结构包括构包括值参、局部变量和返回地址值参、局部变量和返回地址；每每次次执执行行递递归归调调用用之之前前，把把递递归归函函数数的的值值参参和和局局部部变量的当前值以及调用后的返回地址压栈；变量的当前值以及调用后的返回地址压栈；每每次次递递归归调调用用结结束束后后，将将栈栈顶顶元元素素出出栈栈，使使相相应应的的值值参参和和局局部部变变量量恢恢复复为为调调用用前前的的值值，然然后后转转向向返返回回地地址址指定的位置继续执行。指定的位置继续执行。栈的应用举例栈的应用举例栈的应用举例栈的应用举例递归递归递归递归第十一页，本课件共有21页哪些类型的问题适合于用递归方法求

6、解?必须同时具备以下两个条件：必须同时具备以下两个条件：1)一一个个问问题题可可以以化化解解为为若若干干个个性性质质相相同同，解解法法相相同同的的小小问问题题，而而小小问问题题还还可可以以分分解解为为更更小小的的问问题题，上上述述转转化化局局用用相相同的规律，并使问题逐步简化。同的规律，并使问题逐步简化。2)当当问问题题规规模模降降低低到到一一定定程程度度时时是是可可以以直直接接求求解解的的（终终止止条件），即存在明确的递归出口。条件），即存在明确的递归出口。据此，以下类型的问题可以考虑采用递归方法求解：据此，以下类型的问题可以考虑采用递归方法求解：1)数学上定位为递归的函数数学上定位为递归的

7、函数2)数据的结构是递归的数据的结构是递归的例例如如，单单链链表表，它它的的每每个个结结点点的的指指针针域域指指向向下下一一个个结结点点，又又是是一一个个单单链表；树形结构等等链表；树形结构等等3)解题的方式用递归比用递推解法简单解题的方式用递归比用递推解法简单例如，汉诺塔问题，八皇后问题等例如，汉诺塔问题，八皇后问题等第十三页，本课件共有21页如何设计递归程序 递归算法设计的关键在于,找出递归方程和递归终止条件(边界条件).递归关系就是使问题向边界条件转化的过程.因此,递归关系必须能使问题越来越简单,规模越小.因此,递归算法设计,通常有以下3个步骤:(1)分析问题,得出递归关系.(2)设置边

8、界条件,控制递归.(3)设计函数,确定参数.第十四页，本课件共有21页有关递归的知识点有关递归的知识点1.什么是递归程序？递归程序的优缺点是什么？它在执行时应借助于什么来完成？其入口语句、出口语句一般用什么语句实现？1)一个函数在结束之前，直接或间接调用自身称为递归。2)优点：程序结构简单、清晰，易证明其正确性。缺点：难以理解，执行中占内存空间较多，运行效率低3)递归程序在执行中需借助栈来实现。4)递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本项和归纳项组成。基本项是递归程序出口，即不再递归即可求出结果的部分，归纳项是将原来问题化成简单的且与原来形式一样的问题，即向基本项

9、发展，最终到达基本项。第十五页，本课件共有21页有关递归的知识点有关递归的知识点2.一个递归算法必须包括（）A.递归部分 B.终止条件和递归部分 C.迭代部分 D.终止条件和迭代部分B3.当过程P递归调用自身时，过程P内部定义的局部变量在P的2次调用期间是否占用同一数据区？为什么？答：过程P递归调用自身时，过程P内部定义的局部变量在P的2次调用期间不占用同一数据区，每次调用都保留其数据区，这是由递归定义所决定的，用“递归工作栈”来实现。第十六页，本课件共有21页有关递归的知识点有关递归的知识点4.有递归算法如下：int sum(int n)if(n=0)return(0);else scanf

10、(%d,&x);return(sum(n-1)+x)设初值n=4，读入4，9，6，2。问：（1）若x为局部变量，该函数递归调用结束后返回调用程序的sum等于多少？画出递归过程。（2）若 x为全局变量，该函数递归调用结束后返回调用程序的sum等于多少？答：（1）sum=21,当x为局部变量时，每次递归调用都要给局部变量分配存储单元，故x数值4,9,6,2均保留。（2）sum=8，当x为全局变量时，在整个程序执行期间，X只占一个存储单元，先后读入的四个数，仅最后一个起作用，当递归调用结束时，在sum:=sum(n-1)+x 表达式中x就是2，所以结果为sum=2第十七页，本课件共有21页有关递归的

11、知识点有关递归的知识点void test(int&sum)Stack s;InitStack(s);int x;scanf(x);while(x!=0)push(s,x);scanf(x);sum=0;printf(sum);while(!StackEmpty(s)sum+=pop(s);printf(sum);7.将下列递归过程改写为非递归过程 void test(int&sum)int x;scanf(x);if(x=0)sum=0;else test(sum);sum+=x;printf(sum);注：看程序执行过程及结果，设输入5 3 1 0，输出结果应该为0 1 4 9第十九页，本课

12、件共有21页有关递归的知识点有关递归的知识点(1)Ack(2,1)=Ack(1,Ack(2,0)=Ack(1,Ack(1,1)=Ack(1,Ack(0,Ack(1,0)=Ack(1,Ack(0,Ack(0,1)=Ack(1,Ack(0,2)=Ack(1,3)=Ack(0,Ack(1,2)=Ack(0,Ack(0,Ack(1,1)=Ack(0,Ack(0,Ack(0,Ack(1,0)=Ack(0,Ack(0,Ack(0,Ack(0,1)=Ack(0,Ack(0,Ack(0,2)=Ack(0,Ack(0,3)=Ack(0,4)=58.已知Ackerman函数定义如下：习题习题3.27 n+1,当m

13、=0时Ack(m,n)=Ack(m-1,1),当m0,n=0时 Ack(m-1,Ack(m,n-1),当m0,n0时（1）写出Ack(2,1)的计算过程（2）写出计算Ack(m,n)的非递归算法int Ack(int m,int n)if(m=0)return(n+1);else if(m!=0&n=0)return(Ack(m-1,1);else return(Ack(m-1,Ack(m,n-1)第二十页，本课件共有21页有关递归的知识点有关递归的知识点(2)int Ack(int m,int n)int akmmn;int i,j;for(j=0;jn;j+)akm0j=j+1;for(i=1;im;i+)akmi0=akmi-11;for(j=1;jn;j+)akmij=akmi-1akmij-1;return(akmmn);第二十一页，本课件共有21页