《计算机程序设计基础课程教学PPTFOP.ppt》由会员分享，可在线阅读，更多相关《计算机程序设计基础课程教学PPTFOP.ppt（34页珍藏版）》请在三一办公上搜索。
1、乔 林,计算机程序设计基础,Email:Tel:62780973,清华大学计算机科学与技术系,第十二章 递归程序设计,学习目标了解递归可以简化复杂问题的编程实现理解递归程序设计范型理解函数递归调用的内部实现机制熟悉典型递归程序的范例能够编写简单的递归程序,12.1 递归问题的引入,递归的目的简化复杂问题的手段：将问题逐步化简，在化简过程中保持原问题的性质不变，直到问题最简，可以轻易获得答案，然后将简化问题的答案组装成原始问题的解递归示例n!=1 2 3 n:n!=(n-1)!n;0!=1xn=x x x x:xn=xn-1 x;x0=1,递归函数示例一,阶乘的计算,long int CalFa
2、ctorial(int n)long int result=1;int i=0;while(+i=n)result*=i;return result;,long int CalFactorial(int n)long int result;if(n=0|n=1)result=1;else result=n*CalFactorial(n 1);return result;,递归函数示例二,幂的计算,long double CalPower(long double x,int n)long double result;if(n=0)result=1;else result=x*CalPower(x
3、,n 1);return result;,递归函数示例三,求整数的各位数字之和,int SumDigit(int n)if(n 10)return n;else return n%10+SumDigit(n/10);,递归过程的跟踪,阶乘的计算,#include long int CalFactorial(int n)long int result;if(n=0|n=1)result=1;else result=n*CalFactorial(n 1);return result;void main()int num=3;long int fac;fac=CalFactorial(num);pr
4、intf(“%ld”,fac);,递归过程的跟踪,main()函数栈框架,递归过程的跟踪,第一次调用 CalFactorial()函数栈框架,long int CalFactorial(int n)long int result;if(n=0|n=1)result=1;else result=n*CalFactorial(n 1);return result;,递归过程的跟踪,第二次调用 CalFactorial()函数栈框架,long int CalFactorial(int n)long int result;if(n=0|n=1)result=1;else result=n*CalFac
5、torial(n 1);return result;,递归过程的跟踪,第三次调用 CalFactorial()执行后栈框架,long int CalFactorial(int n)long int result;if(n=0|n=1)result=1;else result=n*CalFactorial(n 1);return result;,递归过程的跟踪,第二次调用 CalFactorial()执行后栈框架,long int CalFactorial(int n)long int result;if(n=0|n=1)result=1;else result=n*CalFactorial(n
6、 1);return result;,递归过程的跟踪,第一次调用 CalFactorial()执行后栈框架,long int CalFactorial(int n)long int result;if(n=0|n=1)result=1;else result=n*CalFactorial(n 1);return result;,递归过程的跟踪,控制流返回 main()函数时的栈框架,递归信任与递归范型,理解递归问题的原则不分析复杂细节而仅考虑单一层次上的操作不要跟踪递归调用的栈框架！基本递归假设只要递归调用时的参数比原始参数在某种程度上更简单，则递归调用就一定能获得正确答案递归心理学：这种简单
7、递归调用一定正确工作的假设即为递归信任,12.2 典型递归程序,Hanoi 塔问题假设有三个分别命名为 X、Y 和 Z 的塔座，在塔座 X 上插有 n 个直径大小不同、依小到大分别编号为1，2，n 的圆盘，如图所示。现要求将X 轴上的 n 个圆盘移动到塔座 Z 上并按相同顺序叠放，圆盘移动时必须遵循下述规则：每次只能移动一个圆盘；圆盘可以插在 X、Y 与 Z 中的任意塔座上任何时刻都不能将较大的圆盘压在较小的圆盘上如何实现移动圆盘的操作呢？,Hanoi 塔问题,Hanoi 塔问题,递归算法的伪代码,void MoveHanoiTower(int num,char source,char tem
8、p,char dest)if(n=1)将一个圆盘从 source 移动到 dest else 将 n 1 个圆盘从 source 移动到 temp 将圆盘 n 从 source 移动到 dest 将 n 1 个圆盘从 temp 移动到 dest,Hanoi 塔问题,递归算法,void move(char source,char dest)printf(“%c-%c”,source,dest);void MoveHanoiTower(int num,char source,char temp,char dest)if(num=1)move(source,dest);else MoveHanoiT
9、ower(num 1,source,dest,temp);move(source,dest);MoveHanoiTower(num 1,temp,source,dest);,分形问题,打印一棵对称的分形树分形：部分与整体相似的图形递归：可分解为画树干及其两个树枝的递归过程,分形问题,算法分析层数：在递归过程中层数不断减少，当层数为 0时达到最简长度值及长度变化比例系数：使得长度值根据所处的不同层数而不同角度值及左右分枝对树干的夹角：角度值是树干与水平轴之间的夹角树干顶点坐标值,分形问题,伪代码,if(层数为 0)画树干 else 画树干 计算本树干顶点坐标 在本树干的顶部画左分枝 在本树干的顶
10、部画右分枝,分形问题,算法初步实现,void DrawFractal(double length,double scale,double alpha,double delta,double cx,double cy,int order)if(order=0)画树干，当前点(cx,cy)，长度为length，水平夹角 alpha else 画树干，当前点(cx,cy)，长度 length，水平夹角alpha 计算新的线段顶点坐标(cx,cy)画右分枝，新顶点(cx,cy)，长度 length*scale，水平夹角 alpha delta 画左分枝，新顶点(cx,cy)，长度 length*sca
11、le，水平夹角 alpha+delta,分形问题,算法实现,void DrawLine(double length,double alpha,double cx,double cy)double theta;theta=alpha/180.0*PI;moveto(cx,cy);linerel(length*cos(theta),length*sin(theta);void DrawFractal(double length,double scale,double alpha,double delta,double cx,double cy,int order)if(order=0)DrawLi
12、ne(length,alpha,cx,cy);else DrawLine(length,alpha,cx,cy);cx=cx+length*scale*cos(alpha/180.0*PI);cy=cy length*scale*sin(alpha/180.0*PI);DrawFractal(length*scale,scale,alphadelta,delta,cx,cy,order1);DrawFractal(length*scale,scale,alpha+delta,delta,cx,cy,order1);,其他递归问题一,Pascal 三角形,int PascalTriangle(i
13、nt n,int k)if(k=0|k=n)return 1;else return PascalTriangle(n1,k1)+PascalTriangle(n1,k);,其他递归问题二,折半查找,int BinarySearch(int a,int key,int low,int high)int mid=(low+high)/2;if(low high)return 1;if(key=amid)return mid;else if(key amid)return BinarySearch(a,key,low,mid 1);else return BinarySearch(a,key,mi
14、d+1,high);,一般递归策略,void DoRecursion()if(最简单情况)不使用递归计算简单解 else 将原始问题分解成规模较小的子问题 递归地调用此子程序解决各子问题 将各子问题的解组装成原始问题的解,编写递归程序的原则,递归实现是否检查了最简单情形在尝试将问题分解成子问题前，首先必须检查问题是否已足够简单在大多数情况下，递归子程序以一个if开头，如果程序不是这样，请仔细检查源程序确保您了解所编写代码的准确含义是否解决了最简单情形大量的递归错误都是因为没有正确解决最简单情形所导致的注意，最简单情形不能调用递归,编写递归程序的原则,递归分解是否使得问题更简单只有分解出的子问题
15、越来越简单，递归才能正确工作，否则将形成无限递归，限入死循环。问题的简化过程是否能够确实回归最简单情形，还是遗漏了某些情况例如汉诺塔问题需要调用两次递归过程，程序中如果遗漏了其任意一个都会导致错误,编写递归程序的原则,子问题是否与原始问题完全一致如果递归过程改变了问题的实质，则整个过程肯定会得到错误的结果 使用递归信任时，子问题的解是否正确组装为原始问题的解任务只是递归过程的一部分，将子问题的解正确组装以形成原始问题的解也是必不可少的步骤,12.3 递归与迭代,Fibonacci 数列f(1)=1f(2)=1f(n)=f(n 1)+f(n 2),n 2递归算法的效率远远低于迭代算法,12.3 递归与迭代,递归算法实现,long int Fabonacci(int n)if(n=1|n=2)return 1;else return Fabonacci(n 1)+Fabonacci(n 2);,12.3 递归与迭代,迭代算法实现,long int Fabonacci(int n)int i,f,f1=1,f2=1;if(n=1|n=2)return 1;else for(i=3;i=n;i+)f=f1+f2;f2=f1;f1=f;return f;,作 业,第360页：第三题（编程题）第 7 小题,
