[工学]程序设计基础12.ppt

Modern Operating System 第十二章 递归程序设计 学习目标 了解递归可以简化复杂问题的编程实现 理解递归程序设计范型 理解函数递归调用的内部实现机制 熟悉典型递归程序的范例 能够编写简单的递归程序 12.1 递归问题的引入 递归的目的 简化复杂问题的手段：将问题逐步化简，在化简过程中保持原问题的性质不变，直到问题最简，可以轻易获得答案，然后将简化问题的答案组装成原始问题的解 递归示例 n! = 1 ? 2 ? 3 ? … ? n: n! = (n-1)! ? n; 0! = 1 xn = x ? x ? x ? … ? x: xn = xn-1 ? x; x0 = 1 递归函数示例一 阶乘的计算 递归函数示例二 幂的计算 递归函数示例三 求整数的各位数字之和 递归过程的跟踪 阶乘的计算 递归过程的跟踪 main() 函数栈框架 递归过程的跟踪 第一次调用 CalFactorial() 函数栈框架 递归过程的跟踪 第二次调用 CalFactorial() 函数栈框架 递归过程的跟踪 第三次调用 CalFactorial() 执行后栈框架 递归过程的跟踪 第二次调用 CalFactorial() 执行后栈框架 递归过程的跟踪 第一次调用 CalFactorial() 执行后栈框架 递归过程的跟踪 控制流返回 main() 函数时的栈框架 递归信任与递归范型 理解递归问题的原则 不分析复杂细节而仅考虑单一层次上的操作 不要跟踪递归调用的栈框架！ 基本递归假设 只要递归调用时的参数比原始参数在某种程度上更简单，则递归调用就一定能获得正确答案 递归心理学：这种简单递归调用一定正确工作的假设即为递归信任 12.2 典型递归程序 Hanoi 塔问题 假设有三个分别命名为 X、Y 和 Z 的塔座，在塔座 X 上插有 n 个直径大小不同、依小到大分别编号为1，2，…，n 的圆盘，如图所示。现要求将X 轴上的 n 个圆盘移动到塔座 Z 上并按相同顺序叠放，圆盘移动时必须遵循下述规则： 每次只能移动一个圆盘； 圆盘可以插在 X、Y 与 Z 中的任意塔座上 任何时刻都不能将较大的圆盘压在较小的圆盘上 如何实现移动圆盘的操作呢？ Hanoi 塔问题 Hanoi 塔问题 递归算法的伪代码 Hanoi 塔问题 递归算法 分形问题 打印一棵对称的分形树 分形：部分与整体相似的图形 递归：可分解为画树干及其两个树枝的递归过程 分形问题 算法分析 层数：在递归过程中层数不断减少，当层数为 0时达到最简 长度值及长度变化比例系数：使得长度值根据所处的不同层数而不同 角度值及左右分枝对树干的夹角：角度值是树干与水平轴之间的夹角 树干顶点坐标值 分形问题 伪代码 分形问题 算法初步实现 分形问题 算法实现 其他递归问题一 Pascal 三角形 其他递归问题二 折半查找 一般递归策略 编写递归程序的原则 递归实现是否检查了最简单情形 在尝试将问题分解成子问题前，首先必须检查问题是否已足够简单 在大多数情况下，递归子程序以一个if开头，如果程序不是这样，请仔细检查源程序确保您了解所编写代码的准确含义 是否解决了最简单情形 大量的递归错误都是因为没有正确解决最简单情形所导致的 注意，最简单情形不能调用递归 编写递归程序的原则 递归分解是否使得问题更简单 只有分解出的子问题越来越简单，递归才能正确工作，否则将形成无限递归，限入死循环。 问题的简化过程是否能够确实回归最简单情形，还是遗漏了某些情况 例如汉诺塔问题需要调用两次递归过程，程序中如果遗漏了其任意一个都会导致错误 编写递归程序的原则 子问题是否与原始问题完全一致 如果递归过程改变了问题的实质，则整个过程肯定会得到错误的结果 使用递归信任时，子问题的解是否正确组装为原始问题的解 任务只是递归过程的一部分，将子问题的解正确组装以形成原始问题的解也是必不可少的步骤 12.3 递归与迭代 Fibonacci 数列 f( 1 ) = 1 f( 2 ) = 1 f( n ) = f( n – 1 ) + f( n – 2 ), n 2 递归算法的效率远远低于迭代算法 12.3 递归与迭代 递归算法实现 12.3 递归与迭代 迭代算法实现 作 业 第360页：第三题（编程题） 第 7 小题 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; } * 清华大学计算中心