递归和消去递归.ppt

湖南理工学院计算机与信息工程系 潘理 2005-2-24 - 计算机算法基础 - * 第一章 导引与基本数据结构 主讲：潘理 1.5 递归和消去递归 算法是计算机的灵魂。 没有算法就没有计算机程序。 算法是为解决某些问题而定义的一组清晰的 指令，它对任何正常的输入，都能在有限时 间内得到所需的输出。 一、递归 递归算法是一种强有力的程序设计方法。 直观 易于证明算法的正确性 总的开销通常增加 过程调用和隐式栈管理,重复计算 例1: Euclid算法求最大公因子(m?n?0) gcd(m,n)=gcd(n,m mod n) For example gcd(m,0)= m (why?) gcd(60,24)=gcd(24,12)=gcd(12,0)=12 算法1: Euclid算法求最大公因子 int gcd(int m,int n,) { if (n=0) return m; else return gcd(n,m % n); } 例2: Fibonacci序列 1 if n=1 Fib(n)= 1 if n=2 Fib(n-1)+ Fib(n-2) otherwise Fibonacci序列: 1,1,2,3,5,8,13,??? 算法2: 求Fibonacci数(递归算法) int fib(int n) { if (n?2) return 1; else return fib(n-1)+fib(n-2); } 算法3: 求二叉树的高度 int height(bintree *t) { int h,h1,h2; if (t==NULL) return 0; else{ h1=height(t.left); h2=height(t.right); if (h1h2) h=h1+1; else h=h2+1; return h; } } 算法4: 求数组A[1:n]中的最大元素的最大下标 5 7 4 max1(3)=A[3]=4 max1(2)=A[2]=7 max1(1)=A[2]=7 n=3 A[1:3] int n,A[n],j,k; int max1(int i) { if (i?n) { j= max1(i+1); if (A[i]?A[j]) k=i; else k=j; } else k=n; return k; } i=i+1 i=3 i?3 若调用max1(1) 二、消去递归 在算法设计的的初期阶段使用递归，一旦所设计的递归算法被证明为正确且确信是一个好算法时，就可以消去递归，把该算法翻译成与之等价的、只使用迭代的算法。 直接递归过程的翻译: 用等价非递归代码代替递归调用 对return进行处理 int n,A[n],j,k; int max1(int i) {int j,k; int stack[2n]; top=0; if (i?n) { j= max1(i+1); if (A[i]?A[j]) k=i; else k=j; } else k=n; return k; } L1: top=top+1; stack[top]=i; top=top+1; stack[top]=2; i=i+1; goto L1; L2: j=stack[top]; top=top-1; if (top==0) return k; else { addr=stack[top]; top=top-1; i=stack[top]; top=top-1; top=top+1; stack[top]=k; if (addr=2) goto L2; } 2 算法4: 求数组A[1:n]中的最大元素的最大下标 i=i+1 goto L2 这组规则如下：??? （1）在过程的开始部分，插入说明为栈的代码并将其初始化为空。在一般情况下，这个栈用来存放参数、局部变量和函数的值，每次递归调用的返回地址也要存入栈。 ??? （2）将标号Li附于第一条可执行语句。然后，对于每一处递归调用都用一组执行下列规则的指令来代替。  … … … (见书) 算法4 : 求数组A[1:n]中的最大元素的最大下标 int max3(int n,int *A) { int i=n; int k=n; while (i?1) { i=i-1; if (A[i]?A[k])