递归与迭代程序设计.ppt

上传人:王** 文档编号:188169 上传时间:2023-04-04 格式:PPT 页数:14 大小:81.50KB
下载 相关 举报
递归与迭代程序设计.ppt_第1页
第1页 / 共14页
递归与迭代程序设计.ppt_第2页
第2页 / 共14页
递归与迭代程序设计.ppt_第3页
第3页 / 共14页
递归与迭代程序设计.ppt_第4页
第4页 / 共14页
递归与迭代程序设计.ppt_第5页
第5页 / 共14页
递归与迭代程序设计.ppt_第6页
第6页 / 共14页
递归与迭代程序设计.ppt_第7页
第7页 / 共14页
递归与迭代程序设计.ppt_第8页
第8页 / 共14页
递归与迭代程序设计.ppt_第9页
第9页 / 共14页
递归与迭代程序设计.ppt_第10页
第10页 / 共14页
亲,该文档总共14页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《递归与迭代程序设计.ppt》由会员分享,可在线阅读,更多相关《递归与迭代程序设计.ppt(14页珍藏版)》请在优知文库上搜索。

1、数据结构与算法设计试验数据结构与算法设计试验第三讲第三讲 递归与迭代递归与迭代l 目的目的 分治法的思想分治法的思想递归算法改写成迭代算法的一般方法递归算法改写成迭代算法的一般方法l 重点重点 递归算法理解递归算法理解递归算法改与迭代算法的转化递归算法改与迭代算法的转化l 难点难点将递归算法改写成迭代算法的一般方法和实现将递归算法改写成迭代算法的一般方法和实现一、递归算法的特点一、递归算法的特点3.1 递归递归l 符合人的递推求解问题的自然思维习惯符合人的递推求解问题的自然思维习惯l 算法的结构简单,代码精炼,可读性好算法的结构简单,代码精炼,可读性好l 效率低效率低二、消除递归的一般步骤二、

2、消除递归的一般步骤例例1:写一个递归函数写一个递归函数 reverse (char * s),按逆序输出一个字,按逆序输出一个字符串,并将此递归算法改写成相应的迭代算法。符串,并将此递归算法改写成相应的迭代算法。递归的基本思路递归的基本思路分治分治S为空字符串吗?为空字符串吗?按逆序输出除按逆序输出除S0外的子字符串外的子字符串输出输出S0返回返回YESNO递归算法递归算法void reverse (char * s) if( *s!=0 ) reverse(s+1); putchar (*s); return;输出输出s=”abc”的递归过程的递归过程进入递归调用进入递归调用, top=0递

3、归调用返回递归调用返回, top=6顺序顺序条件条件栈中元素栈中元素top=, s= 顺序顺序条件条件addr, s 1*s=astack1=s, (a)stack2=L2, (putchar)2, s+11top=6addr=stack6s=stack52*s=bstack3=s, (b)stack4=L2 , (putchar)4, s+22top=4addr=stack4s=stack33*s=cstack5=s, (c)stack6=L2 , (putchar)6, s+33top=2addr=stack2s=stack14*s=0调用结束,转返回处理调用结束,转返回处理4top=0完

4、全返回完全返回void reverse (char * s) extern ElemType stack2*n+1, top=0; L1: if( *s!=0 ) stack+top=s; stack+top=L2; s=s+1; goto L1; L2: putchar(*s); / 接下来处理返回语句 if(top=0 ) return; / 栈为空 else addr=stacktop-; / 恢复地址 s=stacktop-; / 恢复参数 if(addr = L2) goto L2; 改写的迭代算法改写的迭代算法void reverse(char * s) int top=0; wh

5、ile(*s!=0) top+; s+; while (top!=0) putchar(*s); s-; top-; 优化后的迭代算法优化后的迭代算法 例例2:写一个求数组:写一个求数组an中的最大元素的递归算法并将其改写中的最大元素的递归算法并将其改写成迭代算法。成迭代算法。ai ai+1 an-1 分治的思路分治的思路:int max (int i) int j=i, k; if(iaj) k=i; else k=j; else k=n-1; return k; 递归算法递归算法:(0) 开始,照搬(所有不涉及递归调用和返开始,照搬(所有不涉及递归调用和返回语句的代码都照搬)回语句的代码都

6、照搬)(1) 定义和初始化堆栈定义和初始化堆栈(存储参数、局部变存储参数、局部变量、返回值和返址量、返回值和返址).int max(int i) extern stack4*n+1, top=0; int j=i, k;(2) 对第一条可执行语句定义标号对第一条可执行语句定义标号L1,每次每次递归调用执行步骤递归调用执行步骤 (3). (3) 将所有参数和局部变量进栈将所有参数和局部变量进栈. (4) 建立第建立第i个返回地址的标号个返回地址的标号Li,进栈,进栈. (5) 计算本次递归调用实参的值,并赋给形计算本次递归调用实参的值,并赋给形参变量参变量.(6) 无条件转移到无条件转移到L1进

7、入递归进入递归. (7) 如果是带返回值的调用,从栈如果是带返回值的调用,从栈顶取回顶取回返回值并代替调用,其余代码按原方式返回值并代替调用,其余代码按原方式处理,并将处理,并将(4)建立的标号附于该语句;建立的标号附于该语句;如果是不带返回值的调用,则将如果是不带返回值的调用,则将(4)建立建立的标号直接附于的标号直接附于(6)对应的语句之后的那对应的语句之后的那条语句条语句. L1: if(in-1) stack+top=i; stack+top=j; stack+top= L2; i=i+1; goto L1; L2: j=stacktop-; if(ai=i; j-) if (ajak

8、) k=j; return k; 优化后的迭代算法优化后的迭代算法 例例3:将分治算法的抽象递归过程改写为迭代过程。:将分治算法的抽象递归过程改写为迭代过程。 SOLUTION DandC (p, q) /* divide and conquer */ int m; SOLUTION s1, s2, s; if( small (p, q) ) s=conquer (p, q); else m=divide (p, q); s1=DandC (p, m); s2=DandC (m+1, q); s=combine (s1, s2); return s; 抽象控制递归算法抽象控制递归算法SOLUT

9、ION DandC (p, q) extern ElemType stack5*n+1, top=0; int m; SOLUTION s1, s2;L1: if(small(p,q) s=conquer(p,q); else m=divide(p,q); stack+top=p; stack+top=q; stack+top=m; stack+top=L2; p=p; q=m; goto L1; L2: s1= stacktop-; stack+top=p; stack+top=q; stack+top=m; stack+top=L3; p=m+1; q=q; goto L1; L3: s2=stacktop-; s=combine(s1,s2); if(top=0) return s; else addr=stacktop-; m=stacktop-; q=stacktop-; p=stacktop-; stack+top=s; if(addr=L2) goto L2; else goto L3; 抽象控制迭代算法抽象控制迭代算法作业 完成实验指导书的递归与迭代程序设计 。考虑将作业二的递归过程改写为迭代过程。

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!