第2章递归.ppt

第2章 递归 递归算法的设计一般分为两步: 第一步，将规模较大的原问题分解为一个或多个规模较小的而又类似于原问题特性的子问题，既将较大的问题递归地用较小的子问题来描述，解原问题的方法同样可以用来解决子问题； 第二步，是确定一个或多个不需要分解、可直接求解的最小子问题。 从上面可以看出，递归调用的过程分为两个阶段： 1）递归过程：将原始问题不断转化为规模小了一级的新问题，从求4！变成求3！，变成求2！，最终达到递归终结条件，求1！； 2）回溯过程：从已知条件出发，沿递归的逆过程，逐一求值返回，直至递归初始处，完成递归调用。 5）增设一个同S栈的成分类型（元素）相同的变量，作为进出栈的缓冲变量，对于递归函数，还需要再增设一个保存函数值中间结果的临时变量，用这个变量替换函数体中的所有函数名，待函数结束之前，在把这个变量的值赋给函数名返回。 6）在原算法的第一条语句之前，增加一条把栈置空的语句。 7）对于递归函数而言，若某条赋值语句中包含两处或多处递归调用（假设为n处），则应首先把它拆成n条赋值语句，使得每条赋值语句只包含一处递归调用，同时对增加的n-1条赋值语句，要增设n-1个局部变量，然后按以上六条规则转换成非递归函数。 第*页 * ⒈教学内容 递归的概念、递归调用的实现原理、递归转换为非递归、汉诺塔问题。 ⒉教学目的 理解递归的特点，会分析什么样的问题适合用递归解决；领会递归调用的执行过程； 了解递归的优点、 了解递归的缺点。 ⒊教学重点 什么样的问题可以用递归解决、递归实现的方法 、递归方法的时空效率。 ⒋教学难点 递归的执行过程，递归转换为非递归。 例1：一个人要搬走10块石头，怎么搬呢？ 例2：计算从1到100的累加和。 例3：计算2n。 这些定义方式体现了一种逻辑思想，同时又是一种解决问题的方案。递归定义的问题，可以用递归的算法来求解。 2.1 引 言 1.问题的提出 n! = 1 n=0 n*(n-1)! n0 Fib( n ) = n n=0,1 Fib(n-1)+ Fib(n-2) n=2 2.递归的概念 递归是一个过程或函数直接或间接调用自身的一种方法，它可以把一个大型的问题层层转化为一个与原问题相似、但规模较小的问题来求解。 数学中阶乘的定义，n的阶乘可以如下表示：  再如，斐波那契（Fibonacci）数列指的是这样一个数列：   直接或间接调用自身的程序称为递归程序。  递归是一种特殊的嵌套调用，是某个函数调用自己，而不是另外一个函数。这是一种函数直接或者间接调用自身编程技术。 2.2 递归调用的实现原理 1.递归算法的构成 能够用递归解决的问题应该满足以下三个条件： 需要解决的问题可以化为一个或多个子问题来求解，而这些子问题的求解方法与原来的问题完全相同，只是在数量规模上不同； 递归调用的次数必须是有限的； 必须有结束递归的条件（边界条件）来终止递归。 2.递归调用的内部过程 【算法2-1】中求阶乘的问题，假设程序运行时，n＝4，那么程序的执行过程。 2.递归调用的内部过程 在这两个阶段中，系统会分别完成一系列的操作。在递归调用之前，系统需完成三件事： 为被调用过程的局部变量分配存储区； 将所有的实参、返回地址等信息传递给被调用过程保存； 将控制转移到被调过程的入口。 从被调用过程返回调用过程之前，系统也应完成三件工作： 保存被调过程的计算结果； 释放被调过程的数据区； 依照被调过程保存的返回地址将控制转移到调用过程。 在计算机中，是通过使用系统栈（后面的章节会介绍“栈”）来完成上述操作的。 递归算法解决问题的方式和特点是：将初始问题可转化为解决方法相同的新问题，而新问题的规模要比原始问题小，新问题又可以转化为规模更小的问题……直至最终归结到最基本的情况——递归的终结条件。 递归方法有许多不利之处，递归调用会占用大量的内存和消耗大量的时间，造成执行效率低。但有时采用递归方法编写的程序简洁、清晰，可读性好。 2.3 递归转换为非递归 1.递归转化为递推 当递归算法所涉及的数据定义形式是递归的情况下，通常可以将递归算法转化为递推算法，用递归的边界条件作为递推的边界条件。比如求阶乘、斐波那契数列等。 递推也是一种从已知条件出发，用一种具体的算法，一步一步接近未知，一般采用循环结构，经常和枚举配合使用。递推算法在求解的过程中，每一个