资源描述：
《2014 acm(1)递归-6》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、•在对问题进行分解、求解的过程中得到的ACM选修课是和原问题性质相同的子问题时，都可以设计出求解该问题的递归算法.递归算法•算法逻辑性强、结构清晰、且算法的正确性易于证明，因此递归是程序设计中一个非常重要的方法。华南师大讲稿华南师大讲稿递归算法的构成例1，求n的阶乘n!（n>0）终止状态：当n=1时，n!=1•递归算法一般由基本项和归纳项两部分组归纳项：当n>1时，n!=n*(n-1)!成。因此，其递归函数可描述如下：intfact(intn)–基本项描述了递归过程的终止状态，即不需要继{续递归而可直接求解的状态；if(n==1)return1;//终止状态
2、–归纳项则描述了如何将一个复杂问题，分解成具elsereturnn*fact(n-1);//归纳项有相同性质的若干子问题，它们解决了，原问题}//fact也就解决了。华南师大讲稿华南师大讲稿递归的执行过程递归方向•从后往前•从前往后华南师大讲稿华南师大讲稿1例2.斐波那齐(Fibonacci)序列1，1，2，3，5，8，1.求单链表的表长——递归算法13，...，定义为F=F=1,F=F+F(i>1)01ii-1i-2于是有：终止状态：当i=0或i=1时，F(i)=1归纳项：当i>1时，F(i)=F(i-1)+F(i-2)因此，其递归函数可描述如下：intF
3、ib(inti){if((i==1)
4、
5、(i==0))return1;//终止状态elsereturnFib(i-1)+Fib(i-2);//归纳项}//Fib华南师大讲稿华南师大讲稿方法一方法二intcounter=0;intLength(structnode*h)voidLength1(structnode*h){{if(h==0)//终止条件if(h==0)//终止条件return0;return;elseelse{counter++;return1+Length(h->next);//递归项Length1(h->next);//递归项}}}华南师大讲
6、稿华南师大讲稿方法三方法四intcounter=0;•voidLength2(structnode*h,int&x){voidLength1(structnode*h)if(h==0)//终止条件{if(h==0)//终止条件return;return;elseelse{x++;{Length2(h->next,x);//递归项Length1(h->next);//递归项counter++;}}}}华南师大讲稿华南师大讲稿2递归的执行过程递归的执行过程•voidLength2(structnode*h,intx)•voidLength2(structnode
7、*h,int&x){{if(h==0)//终止条件if(h==0)//终止条件return;return;elseelse{x++;{x++;Length2(h->next,x);//递归项Length2(h->next,x);//递归项}}}}华南师大讲稿华南师大讲稿2.输出单链表各结点的元素值.方法一voidprint2(structnode*head)//正向输出{if(head==0)return;else{cout<data<<"";print2(head->next);}}华南师大讲稿华南师大讲稿方法二归纳——总结voidprint
8、1(structnode*head)//反向输出{if(head==0)return;else{print1(head->next);cout<data<<"";}}华南师大讲稿华南师大讲稿3练习Recursion.cpp•5.单链表的查找（按序号、按值）•1.求单链表的表长.•6.求一个数组全部元素的和值.•2.输出单链表各结点的元素值.•7.冒泡排序•3.单链表的建立•8.直接选择排序•4.在数组或单链表中找出最大元素值。•9.直接插入排序华南师大讲稿华南师大讲稿问题出栈序列算法设计思路•穷举法–思想：就是用穷举的方法列出所有情况。–算法：
9、用递归算法进行所有情况的搜索。–zju1259华南师大讲稿华南师大讲稿算法设计分析思路(n,0)进栈出栈进栈(3,0)出栈(n-1,1)无法处理而结束进栈出栈(2,1)无法处理而结束(n-2,2)(n-1,0)进栈出栈(2,0)(1,2)(n-3,3)(n-2,1)(n-2,1)无法处理而结束(1,1)无法处理而结束统计(1,1)(1,2)统计(1,0)统计(1,0)统计(1,1)统计统计统计(1,0)统计华南师大讲稿华南师大讲稿4分析思路的改进分析思路•算法stack-out1.cpp(3,0)进栈出栈voidCounter2(intsout,intsin
10、,int&sum)(2,1)无法处理而结束{//si
