算法分析与设计第一二三章4(递归和消去递归)

1、第一章 数学预备知识 第二章 导引与基本数据结构第三章 递归算法武汉科技大学理学院信息与计算科学系杨 波cookie_2008年9月2008-09-01版权所有：杨波，武汉科技大学理学院 递归递归是一种强有力的设计方法递归的效率问题递归的实现机制执行调用时将返回地址进栈为递归子程序准备数据：实参形参值将指令流转入新一级子程序入口处2008-09-01版权所有：杨波，武汉科技大学理学院 执行返回时保存中间计算结果数据从栈顶取出返回地址值按返回地址返回若有变参或函数，进行参数或函数回传递归的满足要求问题P的描述涉及到规模规模发生变化时，问题的性质不发生变化问题的解决有出口，即递归有结束的条件200

2、8-09-01版权所有：杨波，武汉科技大学理学院 递归的表现int P(参数表) if (递归出口) 简单操作 else 简单操作; P; 简单操作; 初始情况递归部分2008-09-01版权所有：杨波，武汉科技大学理学院 阶乘函数阶乘函数定义为：public int Factorial(int n) if(n=0) return 1; return n*Factorial(n-1); 2008-09-01版权所有：杨波，武汉科技大学理学院 斐波那契（Fibonacci）数列 无穷数列1,1,2,3,5,8,13,称为Fibonacci数列，递归定义为： public int F(int n)

3、 if(n=1) return 1; return F(n-1)+F(n-2);时间复杂度：指数阶F(5)= F(4) + F(3) = (F(3) + F(2) + (F(2) + F(1) = (F(2) + F(1) + (F(1) + F(0) + (F(1) + F(0) +1) = (F(1) + F(0) + 1) + (1 +1) +(1 + 1) +1) 2008-09-01版权所有：杨波，武汉科技大学理学院 欧几里德算法求最大公因子算法定义为： public static int GCD(int a,int b) if(b=0) /递归结束条件 return a; retu

4、rn GCD(b,a%b); /递归执行部分GCD(22,8)=GCD(8,22%8)=GCD(8,6)=GCD(6,8%6)=GCD(6,2)=GCD(2,6%2)=GCD(2,0)=22008-09-01版权所有：杨波，武汉科技大学理学院 已知元素x，判断x是否在a1:n中 public static void main(String argv) int x; int a; a=new int5; for(int i=1;in) return 0; else if(aj=x) return j; else return Search(j+1,x,a); 2008-09-01版权所有：杨波，

5、武汉科技大学理学院 整数划分问题将正整数n表示成一系列正整数之和，n=n1+n2+nk，其中n1n2nk1，k1。正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记作p(n)。 例如：正整数6有如下11中不同的划分，所以p(6)=11。6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。 2008-09-01版权所有：杨波，武汉科技大学理学院 在正整数n的所有不同的划分中，将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 q(n,1)=

6、1, n11q(n,m)=q(n,n), mn q(n,n)=1+q(n,n-1) q(n,m)=q(n,m-1)+q(n-m,m), nm1 当最大加数n1不大于1时，任何正整数n只有一种划分形式，即 1+1+1+1最大数n1实际上不能大于n。因此，q(1,m)=1正整数n的划分由n1=n的划分和n1n-1的划分组成 正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1的划分组成 6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。 2008-09-01版权所有：杨波，武汉科技大学理学院 pu

7、blic static int q(int n,int m) if(n1)|(m1) return 0; if(n=1)|(m=1) return 1; if(nm) return q(n,n); if(n=m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); 2008-09-01版权所有：杨波，武汉科技大学理学院 消去递归直接递归消去规则（包括两方面）将递归过程中出现递归的地方，用等价的非递归代码来代替（后面将给出的规则1-7）对return语句做适当处理（后面将给出的规则8-13）2008-09-01版权所有：杨波，武汉科技大学理学院 消去规则消去

8、递归调用过程的开始部分，插入说明为栈的代码并将其初始化为空。（在一般情况下，栈用来存放参数、局部变量、函数的值，和每次递归调用的返回地址。） 将标号Li附于第一条可执行语句。然后，对于每一处递归调用都用一组执行下列规则的指令来代替。 将所有参数和局部变量的值存入栈。栈顶指针可作为一个全局变量来看待。 建立第i个新标号Li，并将i存入栈。这个标号的i值将用来计算返回地址。此标号放在规则7所描述的程序段中。 计算本次调用的各实在参数（可能是表达式）的值，并将这些值赋给相应的形式参数。 插入一条无条件转向语句转向过程的开始部分。 如果这过程是函数，则对递归过程中含有此次函数调用的那条语句作如下处理：

9、将该语句的此次函数调用部分用从栈顶取回该函数值的代码来代替，其余部分的代码按原描述方法照抄，并将4中建立的标号附于这条语句上。如果此过程不是函数，则将4建立的标号附于6所产生的转移语句后面的那条语句。 2008-09-01版权所有：杨波，武汉科技大学理学院 对return语句的处理如果栈为空，则执行正常返回。 否则，将所有输出参数的当前值赋给栈顶上的那些对应的变量。 栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。 从栈中退出所有局部变量和参数的值并把它们赋给对应的变量。 如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在return后面的

10、表达式并将结果值存入栈顶。 用返回地址标号的下标实现对该标号的转向。2008-09-01版权所有：杨波，武汉科技大学理学院 求数组中的最大元素A1:n2008-09-01版权所有：杨波，武汉科技大学理学院 int Max1(int i) int j,k; if(iaj) k=i; else k=j; else k=a.length-1; return k;public int Max2(int i) /java伪代码 int stack; int j,k,addr,n,top; n=a.length()-1; /数组a中存放了待查询的元素 stack=new int2*n+1; /规则1 to

11、p=0; /规则1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /规则8 else /规则9 addr=stacktop;top=top-1; /规则10 i=stacktop;top=top-1; /规则11 top=top+1;stacktop=k; /规则12 if(addr=2) go to L2 /规则13 规则1：过程的开始部分，插入说明为栈的代码并将其初始化为空。（在一般情况下，栈用来存放参数、局部变量、函数的值，和每次递归调用的返回地址。）规则2：将标号Li附于第一条可执行语句。然后，对于每一处递归调用都用一组

12、执行下列规则的指令来代替。规则3：将所有参数和局部变量的值存入栈。栈顶指针可作为一个全局变量来看待。 规则4：建立第i个新标号Li，并将i存入栈。这个标号的i值将用来计算返回地址。此标号放在规则7所描述的程序段中。 规则5：计算本次调用的各实在参数（可能是表达式）的值，并将这些值赋给相应的形式参数。 规则6：插入一条无条件转向语句转向过程的开始部分。 规则7：如果这过程是函数，则对递归过程中含有此次函数调用的那条语句作如下处理：将该语句的此次函数调用部分用从栈顶取回该函数值的代码来代替，其余部分的代码按原描述方法照抄，并将4中建立的标号附于这条语句上。如果此过程不是函数，则将4建立的标号附于6

13、所产生的转移语句后面的那条语句。 规则8：如果栈为空，则执行正常返回。 规则10：栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。 规则11：从栈中退出所有局部变量和参数的值并把它们赋给对应的变量。 规则12：如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在return后面的表达式并将结果值存入栈顶。 规则13：用返回地址标号的下标实现对该标号的转向。 规则9：否则，将所有输出参数的当前值赋给栈顶上对应的那些变量2008-09-01版权所有：杨波，武汉科技大学理学院 012345678910public int Max2(int i) /

14、java伪代码 int stack; int j,k,addr,n,top; n=a.length()-1; /数组a中存放了待查询的元素 stack=new int2*n+1; /规则1 top=0; /规则1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /规则8 else addr=stacktop;top=top-1; /规则10 i=stacktop;top=top-1; /规则11 top=top+1;stacktop=k; /规则12 if(addr=2) go to L2 /规则13 例：求数组a1:5中最大元素

15、的算法，a1=3，a2=10，a3=8，a4=9，a5=412223224k=5addr=2i=45j=5k=4i=34j=4i=24k=2i=12j=22008-09-01版权所有：杨波，武汉科技大学理学院 改进1上述算法只是为了说明一般方法。 对于栈的处理实际上可以采用结构体或类的方式实现，上述stack中分别存放了参数值或者函数返回值和每次函数调用的返回地址（实际为标号的下标，在此均为2）。可以使用二维数组来实现堆栈。 2008-09-01版权所有：杨波，武汉科技大学理学院 public int Max2(int i) /java伪代码 int stack; int j,k,addr,n

16、,top; n=a.length()-1; /数组a中存放了待查询的元素 stack=new intn+12; /规则1 top=0; /规则1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /规则8 else addr=stacktop1; /规则10 i=stacktop0; /规则11 stacktop0=k; /规则12 if(addr=2) go to L2 /规则13 public int Max2(int i) /java伪代码 int stack; int j,k,addr,n,top; n=a.length()

17、-1; /数组a中存放了待查询的元素 stack=new int2*n+1; /规则1 top=0; /规则1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /规则8 else addr=stacktop;top=top-1; /规则10 i=stacktop;top=top-1; /规则11 top=top+1;stacktop=k; /规则12 if(addr=2) go to L2 /规则13 2008-09-01版权所有：杨波，武汉科技大学理学院 改进2由于过程只返回一个地方，所以不必重复存放返回地址。也不需要转向语句。

18、 2008-09-01版权所有：杨波，武汉科技大学理学院 public int Max2(int i) /java伪代码 int stack; int j,k,addr,n,top; n=a.length()-1; /数组a中存放了待查询的元素 stack=new intn+1; top=0; while(iaj) k=i; else k=j; return k; public int Max2(int i) /java伪代码 int stack; int j,k,addr,n,top; n=a.length()-1; /数组a中存放了待查询的元素 stack=new int2*n+1; /规则1 top=0; /规则1L1: if(iaj) k=i; else k=j; else k=n; if(top=0) return k; /规则8 else addr=stacktop;top=top-1; /规则10 i=stacktop;to