递归算法(一)

null递归算法(一)递归算法(一)重庆教育学院 杨华千子程序调用的一般形式：子程序调用的一般形式：1次调用 N次调用 嵌套调用 平行调用系统在实现子程序调用时，要用栈方式管理调用子程序时的返回地址子程序调用的内部操作：子程序调用的内部操作：(1) 在调用时： [返回地址进栈，为被调子程序准备数据，将指令 流转入被调子程序入口] (2) 在返回时： [保存回传值，从栈顶取出返回地址，按返回地址 返回，使用回传值]递归过程的内部实现原理：递归过程的内部实现原理：递归是本质是对自身的嵌套调用递归转化为非递归：递归转化为非递归：求整数a, b的最大公约数(a>b≥0) (1) 用其中一个数a除以另一个数b，得到一个商q1和 一个余数r1； (2) 若r1＝0，则b为a，b的最大公约数；若r1≠0，则 用除数b除以余数r1，得到一个商q2和一个余数r2； (3) 若r2＝0，则r2为a，b的最大公约数；若r2≠0，则 用除数r1除以余数r2，得到一个商q3和一个余数r3； 依次计算，直到rn＝0，此时所得到的rn－1即为所求的最大公约数．递归转化为非递归：递归转化为非递归：求整数a, b的最大公约数(a>b≥0)递归算法(辗转相除) int gcd(int a, int b){ if (b==0) return a; else return gcd(b, a%b); }迭代算法 int gcd2(int a, int b){ while (b!=0){ t=b; b=a%b; a=t; } return a; }递归算法设计：递归算法设计：可以用递归求解的三个条件： (1) 问题P的描述涉及规模； (2) 规模发生变化后，问题的性质不发生变化； (3) 问题的解决有出口(边界)。0/1背包问题－问题描述：0/1背包问题－问题描述：设一背包可容物品的最大质量为m，现有n件物品，质量为m1,m2,…,mn。mi均为正整数，要从n件物品中挑选若干件，使放入背包的质量之和正好为m。 0/1背包问题－递归抽象：0/1背包问题－递归抽象：(1) 先取最后一件物品mn放入背包，若 mn=m，则knap←true。 (2) 若mn0。如果还有可选物 品，即n>1，就变为考虑knap(m-mn,n- 1)；否则考虑knap(m,n-1)。 (3) 若mn>m，则考虑knap(m,n-1)。0/1背包问题－算法描述：0/1背包问题－算法描述：int knap(int m, int n){ int x; x=m-mn; if x>0 sign=1; else if x==0 sign=0; else sign=-1; switch (sign){ case 0: knap=1;break; case 1: if (n>1) if knap(m-mn,n-1) knap=1; else knap= knap(m,n-1); else knap=0; case -1: if (n>1) knap= knap(m,n-1); else knap=0; } }集合划分问题－问题描述：集合划分问题－问题描述：设S是一个具有n个元素的集合S={a1,a2,…,an}，现将S集合划分成K个满足下列条件的子集合S1,S2,…,SK： (1) Si≠φ (2) Si∩Sj=φ (3) S1∪S2∪…∪SK=S 试确定n个元素放入K个无标号盒的划分数S(n,K)。集合划分问题－问题抽象：集合划分问题－问题抽象：n个元素a1,a2,…,an放入K个无标号盒的划分数S(n,K)，在配置过程中存在两种互不相容的情况： (1) {an}是K个子集中的一个子集，则问题转化为把 {a1,a2,…an-1}划分成K-1子集，有：S(n-1,K-1)。 (2) {an}不是K个子集中的一个子集，首先把 {a1,a2,…an-1}划分成K子集，然后把an加入到 其中的一个子集中，有：K*S(n-1,K)集合划分问题－问题抽象：集合划分问题－问题抽象：{a1,a2,…,an}划分成K子集总的划分数： S(n,K)=S(n-1,K-1)+K*S(n-1,K) N>1,k≥1集合划分问题－边界条件：集合划分问题－边界条件： (1) S(n,0)=0 (2) S(n,K)=0 (3) S(n,1)=1 (4) S(n,n)=1集合划分问题－递归关系集合划分问题－递归关系集合划分问题－算法描述：集合划分问题－算法描述：int partion(int n, int k){ int result=0; if (k==0)||(k>n) result=0; else if (k==1)||(k==n) result=1; else result=partion(n-1,k-1)+k*s(n-1,k); return result; }