第 4 章 递 归 教学要求 本章重点 了解递归算法的概念与递归设计要领 掌握应用递归算法求解排序与选择、实现排列组合等典型案例

Presentation on theme: "第 4 章 递 归 教学要求 本章重点 了解递归算法的概念与递归设计要领 掌握应用递归算法求解排序与选择、实现排列组合等典型案例"— Presentation transcript:

1 第 4 章 递 归 教学要求 本章重点 了解递归算法的概念与递归设计要领 掌握应用递归算法求解排序与选择、实现排列组合等典型案例
第 4 章 递 归 教学要求 了解递归算法的概念与递归设计要领 掌握应用递归算法求解排序与选择、实现排列组合等典型案例 了解递归算法中的回溯过程 本章重点 递归关系与边界条件的探求与确定

2 递归概述 1. 递归的概念 (1) 递归（Recursion）是一个过程或函数在其定义中直接或间接调用自身的一种方法，就是利用系统堆栈，实现函数自身调用或相互调用的过程。在通往边界的过程中，都会把单步地址保存下来，再按照先进后出进行运算。 (2) 递归算法通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。 (3) 递归需要有递归关系式与边界条件，递归过程有递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

3 2. 递归方法基本步骤 （1） 根据实际构建递归关系 （2）确定递归边界 （3）编写递归函数 （4）设计主函数调用递归函数

4 3. 举例说明 例4-1 用递归法计算n! 计算整数n的阶乘n!是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。
3. 举例说明 例4-1 用递归法计算n! 计算整数n的阶乘n!是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。 （1）描述递归关系 注意到，当n>1时，n!=n*(n−1)!，这就是一种递归关系。对于特定的k!，它只与k和(k−1)!有关。 （2）确定递归边界 递归边界为: n=1时，n!=1。对于任意给定的n，程序将最终求解到1!。

5 printf(" %d!=%ld \n",n,y); }
long f(int x) { long g; if(x<=0) printf("x<=0, 输入错误！"); else if(x==1) g=1; else g=x*f(x−1); return(g);} （4）设计调用递归函数的主程序 void main() { int n;long y; scanf("%d",&n); y=f(n); // 调用函数f(n) printf(" %d!=%ld \n",n,y); }

6 （5） 递归调用的实现 主函数调用f(n)后即进入函数f(n)执行。 设执行本程序时输入为n=5，即求 5!。在主函数中的调用语句即为y=f(5)，执行f函数，由于n=5，不等于1，故应执行g=n*f(n−1)，即g=5*f(4)。该语句调用f(4),… 进行4次递归调用后，f函数参数值变为1，故不再继续递归调用而开始逐层返回主调函数。f(1)的函数返回值为1，f(2)的返回值为2*1=2，f(3)的返回值为3*2=6，f(4) 的返回值为4*6=24，最后返回值f(5)为5*24=120。

7 4.2 排队购票 案例提出： 一场球赛开始前，售票工作正在紧张进行中。每张球票为50元，有m+n个人排队等待购票，其中有m 个人手持50元的钞票，另外n个人手持100元的钞票。求出这m+n个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数 。（约定：开始售票时售票处没有零钱，拿同样面值钞票的人对换位置为同一种排队。）

8 1. 递归设计要点 令f(m,n)表示有m个人手持50元的钞票，n个人手持100元的钞票时共有的排除总数。 分以下3种情况来讨论。 (1) n=0 n=0意味着排队购票的所有人手中拿的都是50元的钱币，注意到拿同样面值钞票的人对换位置为同一种排队，那么这m个人的排队总数为1，即f(m,0)=1。 (2）m<n 当m<n时，即购票的人中持50元的人数小于持100元的钞票，即使把m张50元的钞票都找出去，仍会出现找不开钱的局面，这时排队总数为0，即f(m,n)=0。

9 (3）其它情况 1） 第m+n个人手持100元的钞票，则在他之前的m+n-1个人中有m个人手持50元的钞票，有n-1个人手持100元的钞票，此种情况共有f(m,n-1)。 2） 第m+n个人手持50元的钞票，则在他之前的m+n-1个人中有m-1个人手持50元的钞票，有n个人手持100元的钞票，此种情况共有f(m-1,n)。 由加法原理得到f(m,n)的递归关系： f(m,n)=f(m,n-1)+f(m-1,n) 初始条件： 当m<n时，f(m,n)=0 当n=0时，f(m,n)=1

10 2. 购票排队的递归描述 long f(int j,int i) {long y; if(i==0) y=1;
2. 购票排队的递归描述 long f(int j,int i) {long y; if(i==0) y=1; else if(j<i) y=0; // 确定初始条件 else y=f(j-1,i)+f(j,i-1); // 实施递归 return(y); }

11 4.3 汉诺塔问题 案例提出： 汉诺塔（Hanoi）问题，又称河内塔问题 。
4.3 汉诺塔问题 案例提出： 汉诺塔（Hanoi）问题，又称河内塔问题 。 （1）有三根桩子A、B、C。A桩上有n个圆盘，最大的一个在底下，其余一个比一个小，依次叠上去。 （2）每次移动一块圆盘，小盘的只能叠在大盘的上面。 （3）把所有圆盘从A桩全部移到C桩上，（如图4-1）。 试求解n个圆盘A桩全部移到C桩上的移动次数，并展示n个圆盘的移动过程。

12 4.3.1 求移动次数 1. 递归设计要点 当n=1时，只一个盘，移动一次即完成。
求移动次数 1. 递归设计要点 当n=1时，只一个盘，移动一次即完成。 当n=2时，首先把小盘从A桩移到B桩；然后把大盘从A桩移到C桩；最后把小盘从B桩移到C桩，移动3次完成。 设移动n个盘的汉诺塔需g(n)次完成。分以下三个步骤： (1) 先将上面n-1个盘借助C从A移到B上，需g(n-1)次； (2) 然后将A桩上第n个盘子移到C桩上（1次）； (3) 最后将B桩上的n-1个盘子借助A移到C，需g(n-1)次。 因而有递归关系：g(n)=2*g(n-1)+1 初始条件(递归出口)：g(1)=1

13 2. 递归设计描述 // 求移动次数的递归函数 double g(int m) { double s; if(m==1) // 确定递归出口 s=1; else s=2*g(m-1)+1; // 实施递归 return s; }

14 展示移动过程 1. 递归设计要点 设递归函数hn(n,a,b,c)展示把n个盘从A桩借助B桩移到C桩的过程,函数mv(a,c)输出从a桩到c桩的过程：A-->C。 完成hn(n,a,b,c)，当n=1时，即mv(a,c)。 当n>1时，分以下三步： (1) 将A上面的n-1个盘借助C移到B，即hn(n-1,a,c,b)； (2) 将A桩上第n个盘子移到C桩上，即mv(a,c)； (3) 将B的n-1个盘借助A移到C，即hn(n-1,b,a,c)。 主程序hn(m,1,2,3)带实参m,1,2,3调用hn(n,a,b,c)，这里m为具体移动盘子的个数。

15 2. 递归设计描述 void mv(char x,char y) // 输出函数 { printf(" %c-->%c ",x,y);
2. 递归设计描述 void mv(char x,char y) // 输出函数 { printf(" %c-->%c ",x,y); k++; // 统计移动次数 if(k%5==0) printf(“\n”); // 输出格式 } void hn(int m,char a,char b,char c) // 递归函数 { if(m==1) mv(a,c); else { hn(m-1,a,c,b);mv(a,c);hn(m-1,b,a,c);}

16 4.5 快速排序与选择 1.逐项比较排序 最简单的排序是把存放在数组的n个数据逐个比较，必要时进行数据交换。
4.5 快速排序与选择 1.逐项比较排序 最简单的排序是把存放在数组的n个数据逐个比较，必要时进行数据交换。 n项逐项比较排序进行升序排序的算法描述如下： for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) if(r[i]>r[j]) {t=r[i];r[i]=r[j];r[j]=t;} 逐项比较排序的时间复杂度为O(n^2)。

17 2. 快速排序 （1）快速排序思路 快速排序又称为分区交换排序，其基本思想是分治，即分而治之：在待排序的n个数据r[1,2,…,n]中任取一个数（例如r[1]）作为基准，把其余n-1个数据分为两个区，小于基准的数放在左边，大于基准的数放在右边。 这样分成的两个区实际上是待排序数据的两个子列。然后对这两个子列分别重复上述分区过程，直到所有子列只有一个元素，即所有元素排到位后，输出排序结果。

18 （2） 分区交换描述 while(i!=j) { while(r[j]>=r[0] && j>i) // 从右至左逐个检查是否大于基准 j=j-1; if(i<j) {r[i]=r[j];i=i+1;} // 把小于基准的一个数赋给r(i) while(r[i]<=r[0] && j>i) // 从左至右逐个检查是否小于基准 i=i+1; if(i<j) {r[j]=r[i];j=j-1;} // 把大于基准的一个数赋给r(j) }

19 （3） 快速排序实现 (见程序c451) （4）快速排序的时间复杂度分析

20 3. 分区交换选择 (1) 选择问题 在一个无序序列r(1),r(2),…,r(n)中，寻找第k小元素的问题称为选择。这里第k小元素是序列按升序排列后的第k个元素。 特别地，当k=n/2时，即寻找位于n个元素中的中间元素，称为中值问题。

21 （2） 选择问题的分区交换设计 参照上述分区交换的快速排序算法，在待选择的n个数据r[1,2,…,n]中任取一个数（例如r[1]）作为基准，把其余n-1个数据分为两个区，小于基准的数放在左边，大于基准的数放在右边，基准定位在s，则 (1) 若s=k，基准数即为所寻求的第k小元素。 (2) 若s>k，可知左边小于该基准数的个数s-1≥k，则在左边的子区继续分区。 (3) 若s<k，可知所寻求的第k小元素在右边子区，则在右边的子区继续分区。 依此（2）（3）继续，直到出现（1）结束，输出结果。

22 (3) 快速选择的时间复杂度分析

23 4.6 排列组合的实现 排列组合是组合数学的基础，从n个不同元素中任取m个，约定1＜m≤n，按任意一种次序排成一列，称为排列，其排列种数记为A(n,m)。 从n个不同元素中任取m个(约定1＜m＜n)成一组，称为一个组合，其组合种数记为C(n,m)。 计算A(n,m)与C(n,m)只要简单进行乘运算即可，要具体展现出排列的每一列与组合的每一组，决非轻而易举。 本节应用递归设计来具体实现排列与组合。

24 实现排列A(n,m) 1. 递归设计要点 递归函数p(k)的变量k从1开始取值。当k≤m时，第k个数a(k)取i(1——n)，并标志量u=0。 （1）若a(k)与其前面已取的数a(j)(j<k)比较，出现a(k)=a(j)，即第k个数取i不成功，标志量u=1。 （2）若a(k)与所有前面已取的a(j)比较，没有一个相等，则第k个数取i成功，标志量保持u=0，然后判断： 1） 若k=m，即已取了m个数，输出这m个数即为一个排列，a(k)继续从i+1开始，在余下的数中取一个数。直到全部取完，则返回上一次调用p(k)处，即回溯到p(k-1)，第k-1个数继续往下取值。 2） 若k<m，即还未取m个数，即在p(k)状态下调用p(k+1)继续探索下一个数，下一个数a(k+1)又从(1——n)中取数。

25 （3）若标志量u=1，第k个数取i不成功，则接着从i+1开始中取下一个数。若在1——n中的每一个数都取了，仍是u=1，则返回上一次调用p(k)处，即回溯到p(k-1)，第k-1个数继续往下取值。
可见递归具有回溯的功能，即p(k)在取所有n个数之后，自动返回调p(k)的上一层，即回溯到p(k-1)，第k-1个数继续往下取值。这也是递归能把所有排列一个不剩全部展示的原因所在。 在主程序，只要调用p(1)即可，所有排列在递归函数中输出。最后返回p(1)的a(1)取完所有数，返回排列个数s，输出排列的个数后结束。 （4）以上实现A(n,m)的递归深度为m，递归算法的时间复杂度为O(mn)。

26 实现组合C(n,m) 注意到组合与组成元素的顺序无关，约定组合中的组成元素按递增排序。因而，把以上排序程序中的约束条件作简单修改: “a[j]==a[i]” 修改为：“ a[j]>=a[i]” “a[k]==a[j]” 修改为 ：“a[k]>=a[j]” 即可实现从n个不同元素中取m个（约定1＜m＜n）的组合C(n,m)。 这样修改实现组合的取值次数、判别次数均与实现排列相同，做了大量无效操作，效率太低。

27 1. 实现组合递归设计 约定组合中的组成元素递增排序，实现a 数组取值的i循环设置为：
for(i=a[k-1]+1;i<=n+k-m;i++) a[k]=i; 循环起点为：a[k-1]+1，即a[k]取值要比a[k-1]大，避免了元素取相同值的判别。 循环终点为：n+k-m，即a[k]最大只能取n+k-m，为后面m-k个元素a[k+1],…,a[m]留下取值空间。 显然a[1]需从1开始取值，因而循环前设置a[0]=0； 递归函数c(k)中，a[k]取值后调用c(k+1)，a[k+1]取值。 当k=m时，输出一个组合；然后a[m]继续往后取值，继续输出组合；直到a[m]取值结束，返回即回溯到前c(m-1)状态， a[m-1] 继续往后取值。 最后c(1)状态中的a[1]取值结束，即返回主程序，输出组合数s。

28 2. 实现可重复的组合递归设计 注意到可重复的组成元素可以相同，因而，把以上递归函数中a[i]的取值范围作简单修改: a[0]=1; for(i=a[k-1];i<=n;i++) 即后一个元素可与前面的元素取值相同，每一个元素都可取到n。这样修改可实现从n个不同元素中取m个（约定1＜m＜n）可重复的组合。 同时，在输出时注明“可重复”。

29 4.8 递归应用小结 递归与递推相比较： （1） 某些计数问题求解，可以相互替换 （2） 在处理展示与构造性案例时，不能相互替代
4.8 递归应用小结 递归与递推相比较： （1） 某些计数问题求解，可以相互替换 例“排队购票”案例求解时，我们用了递归与递推两种算法设计。 （2） 在处理展示与构造性案例时，不能相互替代 例应用递归设计展示汉诺塔移动过程，递推却难以实现。 （3） 递归的求解效率低于递推 递归数据要不断的进栈出栈，且存在大量的重复计算。递推免除了数据进出栈的过程，直接从边界出发，逐步推出函数值，避免了重复计算。因而递推效率远远高于递归。

30 第4章作业 第4章上机 习题4: 1, 2, 3, 4, 5, 6 （1） 上机通过本章汉诺塔问题、快速排序与选择、排列组合的实现等案例；
习题4: 1, 2, 3, 4, 5, 6 第4章上机 （1） 上机通过本章汉诺塔问题、快速排序与选择、排列组合的实现等案例； （2） 上机通过例4-3，比较递归与递推求整数s的划分数的效率 。 （3） 分组讨论并上机通过旋转数阵、整数的拆分等案例。

31 欢迎大家提出教学建议 返回