递归与迭代程序设计.ppt

《递归与迭代程序设计.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; 抽象控制迭代算法抽象控制迭代算法作业 完成实验指导书的递归与迭代程序设计 。考虑将作业二的递归过程改写为迭代过程。