递归程序的设计

栈的应用举例—递归1递归的定义子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。2递归的基本思想问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。3递归的要素⑴递归边界条件：确定递归到何时终止，也称为递归出口；⑵递归模式：大问题是如何分解为小问题的，也称为递归体。栈的应用举例—递归例1阶乘函数递归算法intfact(intn){if(n==0)return1;elsereturnn*fact(n-1);}-*=时当时当)!1(1!n≥1n＝1nnn栈的应用举例—递归求解阶乘n!的过程计算fact(4)计算4*fact(3)计算3*fact(2)计算2*fact(1)计算fact(1)递归调用回归求值返回24返回6返回2返回1栈的应用举例—递归递归过程与递归工作栈递归过程在实现时，需要自己调用自己。层层向下递归，返回次序正好相反：递归调用n!(n-1)!(n-2)!1!=1返回次序栈的应用举例—递归递归函数的内部执行过程每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。局部变量返回地址值参活动记录框架递归工作记录⑴运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；⑵每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；⑶每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。栈的应用举例—递归哪些类型的问题适合于用递归方法求解?必须同时具备以下两个条件：1)一个问题可以化解为若干个性质相同，解法相同的小问题，而小问题还可以分解为更小的问题，……上述转化局用相同的规律，并使问题逐步简化。2)当问题规模降低到一定程度时是可以直接求解的（终止条件），即存在明确的递归出口。据此，以下类型的问题可以考虑采用递归方法求解：1)数学上定位为递归的函数2)数据的结构是递归的例如，单链表，它的每个结点的指针域指向下一个结点，又是一个单链表；树形结构等等3)解题的方式用递归比用递推解法简单例如，汉诺塔问题，八皇后问题等如何设计递归程序递归算法设计的关键在于,找出递归方程和递归终止条件(边界条件).递归关系就是使问题向边界条件转化的过程.因此,递归关系必须能使问题越来越简单,规模越小.因此,递归算法设计,通常有以下3个步骤:(1)分析问题,得出递归关系.(2)设置边界条件,控制递归.(3)设计函数,确定参数.有关递归的知识点1.什么是递归程序？递归程序的优缺点是什么？它在执行时应借助于什么来完成？其入口语句、出口语句一般用什么语句实现？1)一个函数在结束之前，直接或间接调用自身称为递归。2)优点：程序结构简单、清晰，易证明其正确性。缺点：难以理解，执行中占内存空间较多，运行效率低3)递归程序在执行中需借助栈来实现。4)递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本项和归纳项组成。基本项是递归程序出口，即不再递归即可求出结果的部分，归纳项是将原来问题化成简单的且与原来形式一样的问题，即向基本项发展，最终到达基本项。有关递归的知识点2.一个递归算法必须包括（）A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分B3.当过程P递归调用自身时，过程P内部定义的局部变量在P的2次调用期间是否占用同一数据区？为什么？答：过程P递归调用自身时，过程P内部定义的局部变量在P的2次调用期间不占用同一数据区，每次调用都保留其数据区，这是由递归定义所决定的，用“递归工作栈”来实现。有关递归的知识点4.有递归算法如下：intsum(intn){if(n==0)return(0);else{scanf(%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有关递归的知识点voidtest(int&sum){Stacks;InitStack(s);intx;scanf(x);while(x!=0){push(s,x);scanf(x);}sum=0;printf(sum);while(!StackEmpty(s)){sum+=pop(s);printf(sum);}}7.将下列递归过程改写为非递归过程voidtest(int&sum){intx;scanf(x);if(x==0)sum=0;else{test(sum);sum+=x;}printf(sum);}注：看程序执行过程及结果，设输入5310，输出结果应该为0149有关递归的知识点(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.27n+1,当m=0时Ack(m,n)=Ack(m-1,1),当m0,n=0时Ack(m-1,Ack(m,n-1)),当m0,n0时（1）写出Ack(2,1)的计算过程（2）写出计算Ack(m,n)的非递归算法intAck(intm,intn){if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ack(m-1,1));elsereturn(Ack(m-1,Ack(m,n-1)))}有关递归的知识点(2)intAck(intm,intn){intakm[m][n];inti,j;for(j=0;jn;j++)akm[0][j]=j+1;for(i=1;im;i++){akm[i][0]=akm[i-1][1];for(j=1;jn;j++)akm[i][j]=akm[i-1][akm[i][j-1]];}return(akm[m][n]);}