《程序设计基础12》由会员分享，可在线阅读，更多相关《程序设计基础12（33页珍藏版）》请在金锄头文库上搜索。
1、1清华大学计算中心http:/计算机程序设计基础第十二章 递归程序设计 学习目标 了解递归可以简化复杂问题的编程实现 理解递归程序设计范型 理解函数递归调用的内部实现机制 熟悉典型递归程序的范例 能够编写简单的递归程序2清华大学计算中心http:/计算机程序设计基础12.1 递归问题的引入 递归的目的 简化复杂问题的手段：将问题逐步化简，在化简 过程中保持原问题的性质不变，直到问题最简， 可以轻易获得答案，然后将简化问题的答案组装 成原始问题的解 递归示例 n! = 1 2 3 n: n! = (n-1)! n; 0! = 1 xn = x x x x: xn = xn-1 x; x0 = 1
2、3清华大学计算中心http:/计算机程序设计基础递归函数示例一 阶乘的计算long long intint CalFactorialCalFactorial( ( intint n n ) )long long intint resultresult = 1; = 1;intint i i = 0; = 0;while( + while( +i i long long intint CalFactorialCalFactorial( ( intint n n ) )long long intint resultresult; ;if( if( n n = 0 | = 0 | n n = 1 )
3、 = 1 ) resultresult = 1; = 1;else else resultresult = = n n * * CalFactorialCalFactorial( ( n n 1 ); 1 );return return resultresult; ; void void mainmain()()intint numnum = 3; long = 3; long intint facfac; ;facfac = = CalFactorialCalFactorial( ( numnum ); );printfprintf( “%( “%ldld”, ”, facfac ); );
4、 7清华大学计算中心http:/计算机程序设计基础递归过程的跟踪 main() 函数栈框架8清华大学计算中心http:/计算机程序设计基础递归过程的跟踪 第一次调用 CalFactorial() 函数栈框架9清华大学计算中心http:/计算机程序设计基础递归过程的跟踪 第二次调用 CalFactorial() 函数栈框架10清华大学计算中心http:/计算机程序设计基础递归过程的跟踪 第三次调用 CalFactorial() 执行后栈框架11清华大学计算中心http:/计算机程序设计基础递归过程的跟踪 第二次调用 CalFactorial() 执行后栈框架12清华大学计算中心http:/计算机
5、程序设计基础递归过程的跟踪 第一次调用 CalFactorial() 执行后栈框架13清华大学计算中心http:/计算机程序设计基础递归过程的跟踪 控制流返回 main() 函数时的栈框架14清华大学计算中心http:/计算机程序设计基础递归信任与递归范型 理解递归问题的原则 不分析复杂细节而仅考虑单一层次上的操作 不要跟踪递归调用的栈框架！ 基本递归假设 只要递归调用时的参数比原始参数在某种程度上 更简单，则递归调用就一定能获得正确答案 递归心理学：这种简单递归调用一定正确工作的 假设即为递归信任15清华大学计算中心http:/计算机程序设计基础12.2 典型递归程序 Hanoi 塔问题 假
6、设有三个分别命名为 X、Y 和 Z 的塔座，在塔 座 X 上插有 n 个直径大小不同、依小到大分别编 号为1，2，n 的圆盘，如图所示。现要求将 X 轴上的 n 个圆盘移动到塔座 Z 上并按相同顺序 叠放，圆盘移动时必须遵循下述规则：每次只能移动一个圆盘； 圆盘可以插在 X、Y 与 Z 中的任意塔座上任何时刻都不能将较大的圆盘压在较小的圆盘上 如何实现移动圆盘的操作呢？ 16清华大学计算中心http:/计算机程序设计基础Hanoi 塔问题17清华大学计算中心http:/计算机程序设计基础Hanoi 塔问题 递归算法的伪代码void void MoveHanoiTowerMoveHanoiTow
7、er( ( intint numnum, char , char sourcesource, char , char temptemp, char , char destdest ) ) if( if( n n = 1 ) = 1 )将一个圆盘从将一个圆盘从 sourcesource 移动到移动到 destdestelse else 将将 n n 1 1 个圆盘从个圆盘从 sourcesource 移动到移动到 temptemp将圆盘将圆盘 n n 从从 sourcesource 移动到移动到 destdest将将 n n 1 1 个圆盘从个圆盘从 temptemp 移动到移动到 destde
8、st 18清华大学计算中心http:/计算机程序设计基础Hanoi 塔问题 递归算法void void movemove( char ( char sourcesource, char , char destdest ) )printfprintf( “%( “%c c- -%c c”, ”, sourcesource, , destdest ); ); void void MoveHanoiTowerMoveHanoiTower( ( intint numnum, char , char sourcesource, char , char temptemp, char , char dest
9、dest ) )if( if( numnum = 1 ) = 1 ) movemove( ( sourcesource, , destdest ); ); else elseMoveHanoiTowerMoveHanoiTower( ( num num 1, 1, sourcesource, , destdest, , temp temp ); );movemove( ( sourcesource, , destdest ); );MoveHanoiTowerMoveHanoiTower( ( num num 1, 1, temptemp, , sourcesource, , destdest
10、 ); ); 19清华大学计算中心http:/计算机程序设计基础分形问题 打印一棵对称的分形树 分形：部分与整体相似的图形 递归：可分解为画树干及其两个树枝的递归过程20清华大学计算中心http:/计算机程序设计基础分形问题 算法分析 层数：在递归过程中层数不断减少，当层数为 0 时达到最简 长度值及长度变化比例系数：使得长度值根据所 处的不同层数而不同 角度值及左右分枝对树干的夹角：角度值是树干 与水平轴之间的夹角 树干顶点坐标值21清华大学计算中心http:/计算机程序设计基础分形问题 伪代码if( if( 层数为层数为 0 ) 0 ) 画树干画树干 elseelse 画树干画树干计算本树
11、干顶点坐标计算本树干顶点坐标在本树干的顶部画左分枝在本树干的顶部画左分枝在本树干的顶部画右分枝在本树干的顶部画右分枝 22清华大学计算中心http:/计算机程序设计基础分形问题 算法初步实现void void DrawFractalDrawFractal( double ( double lengthlength, double , double scalescale, double , double alphaalpha, double , double deltadelta, double , double cxcx, double , double cycy, , intint orde
12、r order ) ) if( if( orderorder = 0 ) = 0 ) 画树干，当前点画树干，当前点 ( (cxcx, , cycy) )，长度为长度为lengthlength，水平夹角水平夹角 alphaalpha elseelse 画树干，当前点画树干，当前点 ( (cxcx, , cycy) )，长度长度 lengthlength，水平夹角水平夹角alphaalpha计算新的线段顶点坐标计算新的线段顶点坐标 ( (cxcx, , cycy) )画右分枝，新顶点画右分枝，新顶点 ( (cxcx, , cycy) )，长度，长度 length length * * scales
13、cale，水平夹角水平夹角 alpha alpha deltadelta画左分枝，新顶点画左分枝，新顶点 ( (cxcx, , cycy) )，长度，长度 length length * * scalescale，水平夹角水平夹角 alpha alpha + + deltadelta 23清华大学计算中心http:/计算机程序设计基础分形问题 算法实现void void DrawLineDrawLine( double ( double lengthlength, double , double alphaalpha, double , double cxcx, double , double
14、 cycy ) )double double thetatheta; ; theta theta = = alpha alpha / 180.0 * / 180.0 * PIPI; ;movetomoveto( ( cxcx, , cycy ); ); linerellinerel( ( length length * * coscos( (thetatheta), ), length length * * sinsin( (thetatheta) );) ); void void DrawFractalDrawFractal( double ( double lengthlength, double , double scalescale, double , double alphaalpha, ,double double deltadelta, double , double cxcx, double , double cycy, , intint order order ) )if( if( order o
