算法与结构课件第二章递归(华北电力大学科技学院).ppt

计算机算法设计与分析 NorthChinaElectricPowerUniversity ComputerAlgorithmsDesign Analysis 华北电力大学计算机科学与工程系 Dept ofComputerScience EngineeringofNorthChinaElectricPowerUniversity 第二章递归 Recursion 递归的概念 递归算法的应用和实现 递归问题的非递归算法 NorthChinaElectricPowerUniversity 递归方程渐进阶的求法 生成函数 1递归的概念 NorthChinaElectricPowerUniversity 一个直接或间接调用自身的算法称为递归算法 一个使用函数自身给出定义的函数称为递归函数 例阶乘函数阶乘函数的定义为 n 1n 0 n n 1 n 0 定义式的左右两边都引用了阶乘记号 是一个递归定义式 可递归地定义如下 intFactorial intn if n 0 return1 returnn Factorial n 1 2递归算法的应用和实现 如果问题的数据结构是递归的 问题的定义是递归的 问题的解法是递归的 可以考虑用递归算法 看下面的数据结构 Head Head 这是单链表 每个结点有两个域 数据域和指针域 它是一种递归的结构 可定义为 1 一个结点 其指针域为null 是一个单链表 2 一个结点 其指针域为有效指针指向一个单链表 仍是一个单链表 1 问题的数据结构是递归的 NorthChinaElectricPowerUniversity 若存在如上定义的一个单链表 现要实现打印最后一个结点的数据域的值 可用下面递归过程 templateclasslink list Typedata link list next templatevoidsearch1 link list h if h next null coutdata elsesearch1 h next NorthChinaElectricPowerUniversity NorthChinaElectricPowerUniversity 二叉树 BinaryTree 也是一种递归的数据结构 其递归定义为 1 它是一棵空树 2 它是由一个根结点和两棵分别称为左右子树的二叉树构成 要遍历一棵二叉树可以采用下面的递归算法 voidTraverse Bitptr t if t null coutdata Traverse t lchild Traverse t rchild NorthChinaElectricPowerUniversity 例 Fibonacci数列无穷数列1 1 2 3 5 8 13 21 34 55 称为Fibonacci数列 它可以递归地定义为 Fib n 1n 0 1n 1 Fib n 1 Fib n 2 n 1 第n个Fibonacci数可递归地计算如下 intFibonacci intn if n 1 return1 returnFibonacci n 1 Fibonacci n 2 上述两例中的函数也可用如下非递归方式定义 n 1 2 3 n 1 2 问题的定义是递归的 NorthChinaElectricPowerUniversity 例 整数划分问题 将一个正整数n表示成一系列正整数之和 n n1 n2 nk 其中n1 n2 nk 1 k 1正整数n的一个这种表示称为正整数n的一个划分 正整数n的不同划分个数称为正整数n的划分数 记做p n 如正整数6有如下11种不同的划分 所以p 6 11 6 5 1 4 2 4 1 1 3 3 3 2 1 3 1 1 1 2 2 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1 3 问题的解法是递归的 NorthChinaElectricPowerUniversity 在正整数n的所有不同的划分中 将最大加数n1不大于m的划分个数记作q n m 我们可以建立如下递归关系 1 q n 1 1 n 1 当最大加数n1不大于1时 任何正整数n只有一种划分形式 2 q n m q n n m n 最大加数n1实际上不能大于n 因此 q n m q n n 3 q n n 1 q n n 1 正整数n的划分由n1 n和n1 n 1的划分组成 4 q n m q n m 1 q n m m n m 1 正整数n的最大加数n1不大于m的划分由n1 m的划分和n1 m 1的划分组成 以上的关系实际上给出了计算q n m 的递归式如下 q n m 1m 1 q n n n m 1 q n n 1 n m q n m 1 q n m m n m 1 0n 1或m 1 递归算法的设计方法 递归算法既是一种有效的算法设计方法 也是一种有效的分析问题的方法 递归算法求解问题的基本思想是 对于一个较为复杂的问题 把原问题分解成若干个相对简单且类同的子问题 这样 原问题就可递推得到解 适宜于用递归算法求解的问题的充分必要条件是 1 问题具有某种可借用的类同自身的子问题描述的性质 2 某一有限步的子问题 也称作本原问题 有直接的解存在 当一个问题存在上述两个基本要素时 该问题的递归算法的设计方法是 1 把对原问题的求解设计成包含有对子问题求解的形式 2 设计递归出口 例设计模拟汉诺塔问题求解过程的算法 汉诺塔问题的描述是 设有3根标号为A B C的柱子 在A柱上放着n个盘子 每一个都比下面的略小一点 要求把A柱上的盘子全部移到C柱上 移动的规则是 1 一次只能移动一个盘子 2 移动过程中大盘子不能放在小盘子上面 3 在移动过程中盘子可以放在A B C的任意一个柱子上 问题分析 可以用递归方法求解n个盘子的汉诺塔问题 基本思想 1个盘子的汉诺塔问题可直接移动 n个盘子的汉诺塔问题可递归表示为 首先把上边的n 1个盘子从A柱移到B柱 然后把最下边的一个盘子从A柱移到C柱 最后把移到B柱的n 1个盘子再移到C柱 4个盘子汉诺塔问题的递归求解示意图如图6 4所示 图6 4汉诺塔问题的递归求解示意图 Y X Z 以三个盘为例 A B C 算法设计 首先 盘子的个数n是必须的一个输入参数 对n个盘子 我们可从上至下依次编号为1 2 n 其次 输入参数还需有3个柱子的代号 我们令3个柱子的参数名分别为fromPeg auxPeg和toPeg 最后 汉诺塔问题的求解是一个处理过程 因此算法的输出是n个盘子从柱子fromPeg借助柱子auxPeg移动到柱子toPeg的移动步骤 我们设计每一步的移动为屏幕显示如下形式的信息 MoveDiskifromPegXtoPegY这样 汉诺塔问题的递归算法可设计如下 voidtowers intn charfromPeg chartoPeg charauxPeg if n 1 递归出口 printf s c s c n movedisk1frompeg fromPeg topeg toPeg return 把n 1个圆盘从fromPeg借助toPeg移至auxPegtowers n 1 fromPeg auxPeg toPeg 把圆盘n由fromPeg直接移至toPegprintf s d s c s c n movedisk n frompeg fromPeg topeg toPeg 把n 1个圆盘从auxPeg借助fromPeg移至toPegtowers n 1 auxPeg toPeg fromPeg 测试主函数如下 includevoidmain void Towers 4 A C B 程序运行的输出信息如下 MoveDisk1fromPegAtoPegBMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk3fromPegAtoPegBMoveDisk1fromPegCtoPegAMoveDisk2fromPegCtoPegBMoveDisk1fromPegAtoPegBMoveDisk4fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk2fromPegBtoPegAMoveDisk1fromPegCtoPegAMoveDisk3fromPegBtoPegCMoveDisk1fromPegAtoPegBMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegC 总结如下 递归算法的执行过程是不断地自调用 直到到达递归出口才结束自调用过程 到达递归出口后 递归算法开始按最后调用的过程最先返回的次序返回 返回到最外层的调用语句时递归算法执行过程结束 代码 递归过程的实现 对于非递归函数 调用函数在调用被调用函数前 系统要保存以下两类信息 1 调用函数的返回地址 2 调用函数的局部变量值 当执行完被调用函数 返回调用函数前 系统首先要恢复调用函数的局部变量值 然后返回调用函数的返回地址 递归函数被调用时 系统要作的工作和非递归函数被调用时系统要作的工作在形式上类同 但保存信息的方法不同 递归函数被调用时 系统的运行时栈也要保存上述两类信息 每一层递归调用所需保存的信息构成运行时栈的一个工作记录 在每进入下一层递归调用时 系统就建立一个新的工作记录 并把这个工作记录进栈成为运行时栈新的栈顶 每返回一层递归调用 就退栈一个工作记录 因为栈顶的工作记录必定是当前正在运行的递归函数的工作记录 所以栈顶的工作记录也称为活动记录 设计举例 一般递归算法设计举例 例1设计一个输出如下形式数值的递归算法 nnn n 333221 问题分析 该问题可以看成由两部分组成 一部分是输出一行值为n的数值 另一部分是原问题的子问题 其参数为n 1 当参数减到0时不再输出任何数据值 因此递归的出口是当参数n 0时空语句返回 算法设计 递归算法设计如下 voidDisplay intn inti for i 1 i0 Display n 1 递归 n 0为递归出口 递归出口为空语句 代码 例6 6设计求解委员会问题的算法 委员会问题是 从一个有n个人的团体中抽出k k n 个人组成一个委员会 计算共有多少种构成方法 问题分析 从n个人中抽出k k n 个人的问题是一个组合问题 把n个人固定位置后 从n个人中抽出k个人的问题可分解为两部分之和 第一部分是第一个人包括在k个人中 第二部分是第一个人不包括在k个人中 对于第一部分 则问题简化为从n 1个人中抽出k 1个人的问题 对于第二部分 则问题简化为从n 1个人中抽出k个人的问题 图6 7给出了n 5 k 2时问题的分解示意图 图6 7委员会问题分解示意图 当n k或k 0时 该问题可直接求解 数值均为1 这是算法的递归出口 因此 委员会问题的递推定义式为 intComm intn intk if nn return0 if k 0 return1 if n k return1 returnComm n 1 k 1 Comm n 1 k 例6 7求两个正整数n和m最大公约数的递推定义式为 要求 1 编写求解该问题的递归算法 2 分析当调用语句为Gcd 30 4 时算法的执行过程和执行结果 3 分析当调用语句为Gcd 97 5 时算法的执行过程和执行结果 4 编写求解该问题的循环结构算法 解 1 递归算法如下 intGcd intn intm if nn returnGcd m n elsereturnGcd m n m 2 调用语句为Gcd 30 4 时 因m n 递归调用Gcd 4 2 因m n 递归调用Gcd 2 0 因m 0 到达递归出口 函数最终返回值为n 2 即30和4的最大公约数为2 3 调用语句为Gcd 5 97 时 因m n 递归调用Gcd 97 5 因m n 递归调用Gcd 5 2 因m n 递归调用Gcd 2 1 因m n 递归调用Gcd 1 0 因m 0 到达递归出口 函数最终返回值为n 1 即5和97的最大公约数为1 4 编写求解该问题的循环结构算法 代码 Fibn 3f1 1f2 1f 2 Fibn 2f1 1f2 0f 1 Fibn 1f1 f2 f 1 Fibn 1f1 f2 f 1 Fibn 0f1 f2 f 0 NorthChinaElectricPowerUniversity q n m 1m 1 q n n n m 1 q n n 1 n m q n m 1 q n m m n m 1 0n 1或m 1 q 6 6 q 6 5 q 6 4 q 1 5 q 6 3 q 2 4 q 6 2 q 3 3 q 6 1 q 4 2 q 4 1 q 2 2 q 2 1 q 3 2 q 3 1 q 1 2 q 1 1 q 2 2 q 2 1 q 1 1 1 1 1 1 1 1 1 2 3 4 1 1 1 2 3 7 1 2 2 9 1 1 10 11 q 6 1 1q 2 1 1q 4 1 1q 2 2 2q 2 1 1q 2 4 2q 2 2 2q 6 4 9q 4 2 3q 1 1 1q 6 2 4q 1 5 1q 3 1 1q 6 5 10q 1 1 1q 6 6 11q 1 2 1q 3 2 2q 3 3 3q 6 3 7 NorthChinaElectricPowerUniversity NorthChinaElectricPowerUniversity 3递归问题的非递归算法 一般说来 递归过程的实现效率是非常低的 每次递归调用都必须首先做诸如参数替换 环境保护等事情 造成效率低下的另一个重要的原因是大量的重复计算 Fib 5 的计算过程 Fib 0 计算3次 Fib 1 计算5次 Fib 2 计算3次 Fib 3 计算2次 Fib 4 计算1次 Fib n Fib n 1 Fib n 2 n 1 NorthChinaElectricPowerUniversity Fib 5 Fib 4 Fib 3 Fib 3 Fib 2 Fib 2 Fib 2 Fib 1 Fib 1 Fib 0 Fib 1 Fib 0 Fib 1 Fib 0 Fib 1 将递归算法转化成非递归算法的方法 1 设计迭代算法 如果一个函数既有递归形式的定义又有非递归的迭代形式的定义 则可以用循环结构设计出迭代算法 一般说来 如果在一个函数或过程中只递归调用它一次 那么它的计算或执行过程可以看成是线性变化的 n n 1 n 2 1 0 从顶到底递归 从底到顶返回 NorthChinaElectricPowerUniversity intFact intn if n 0 return1 elsereturnn Fact n 1 intFact2 intn x 1 for i 1 i n i x i x returnx 以Fibnaocci数列为例 看非递归算法的转化 Fib 5 Fib 4 Fib 3 Fib 3 Fib 2 Fib 2 Fib 1 Fib 2 Fib 1 Fib 1 Fib 0 Fib 1 Fib 0 Fib 1 Fib 0 Fib 5 Fib 4 Fib 3 Fib 2 Fib 0 Fib 1 NorthChinaElectricPowerUniversity intFib2 intn if n 2 return n else inty 0 intx 1 intz for inti 2 i n i z y y x x z y return x 2 消除尾递归 递归调用是最后一步操作 可以用循环结构通过设置一些工作单元 把递归算法转化为非递归算法 开始令工作单元等于外层的实际参数 以后随着循环的执行 不断向里层变化 直到原递归调用的最里层的情况 循环结束后 执行原属于最里层的操作 而后整个算法结束 NorthChinaElectricPowerUniversity 例 寻找单链表的最后一个结点并打印其数据域的值的过程search就是一个尾递归过程 templateclasslink list Typedata link list next voidsearch h link list if h next null cout h data elsesearch h next voidsearch2 link listh p h 给工作单元赋值 最外层的实际参数while p next null p p next 向里推进一层cout p data 执行最里层的操作 NorthChinaElectricPowerUniversity 递归的实现是基于堆栈的 当一个递归问题不容易找到它的迭代算法又不属于尾递归时 通常通过引入一个工作栈保存 返回位置 以实现过程调用一返回控制 这一思想同样适用于递归消除 下面以先根遍历为例 具体讨论如何用工作栈消除递归 首先必须弄清工作栈的作用方式 即弄清怎样用工作栈控制先根遍历的 走向 二叉链表上的任一X以及它的左XL和右子树XR 假设t是指向结点X的指针 3 利用堆栈 NorthChinaElectricPowerUniversity 1 树的先序遍历的非递归实现 NorthChinaElectricPowerUniversity 由先根遍历的定义可知 当遍历到结点X 即执行preorder t 时 有三项需顺序完成的工作 访问 根子树的 结点X 遍历XL 与调用preorder t lchild 对应 遍历XR与调用preorder t rchild 对应 其中 与 的连接没问题 但 与 如何连接需要考虑 为了做 必须 知道 XR的 根指针 即结点X的右指针t rchild 可是X的左子树XL上没有这个指针 因此 应该在做 之前便将指针t rchild保存起来 并当任务 完成之后 取出 该指针以便执行任务 在这以后 指针t rchild就没有保存价值了 对于先根遍历来说 完成了任务 也就完成了对以X为根的整个子树的遍历 可以直接退回到X的父结点 NorthChinaElectricPowerUniversity 根据以上分析 先根遍历的非递归算法需引入任务栈以保存每个结点的右指针 这样 非递归算法在二叉链表的任一结点X上的主要操作步骤可归纳如下 访问结点X 结点X的右指针进栈 若XL不空 沿X的左指针遍历XL 从栈中取出X的右指针并将其退栈 若XR不空 沿X右指针遍历XR 需要特别考虑的是 在二叉链表上 对任一结点X的任何操作都必须借助于指向它的指针的指引才能进行 而这一指针存在于X的父结点的某个指针域中 唯一的例外是根结点 指向它的指针是根指针 为了统一处理这两种情况 可在算法的初始化中先将指针进栈 而在循环体的开头做取栈顶操作 这样 第一次从栈中取出的正是根指针 而以后栈中存储 并取出 的是各个结点的右指针 NorthChinaElectricPowerUniversity 综合以上考虑 先根遍历非递归算法的非形式描述如下 根指针进栈 while 栈不空 s 栈顶元素 退栈 while s NULL 根或左 右子树不空时继续遍历 visit s s rchild进栈 保存右指针 s s lchild 准备遍历左子树 NorthChinaElectricPowerUniversity voidpreorder1 bitreptrt 先根遍历根结点为t的二叉树 bitreptrstack stacksize 工作栈 inttop top 0 stack top t 根指针进栈 while top 0 s stack top 读栈顶元素到S中 top 退栈 while s NULL visit s top stack top s rchild 右指针进栈保存 s s lchild 修改s以便继续遍历左子树 通过上面的例子可以看出 工作栈在消除递归中的基本作用是提供一种控制机构 在非递归算法执行过程中的某些 关键 时刻 用栈顶元素来 引导 下一步操作的 走向 为了达到这一目的 必须提前将这些有用的信息进栈保存 在上面的例子中 工作栈保存的是各个结点的右指针 这些指针也就是二叉树上各结点的右子树的根指针 显然 这些根指针正是先根遍历递归算法中包含的一些递归调用的实参 这些实参在非递归算法中若不及时保存就会丢失 因此 递归算法中的调用一返回控制被工作栈的作用所取代 从而将递归算法转换成非递归算法 NorthChinaElectricPowerUniversity 2 n 的非递归实现 首先设定一个工作记录栈S 其类型定义如下 definemaxsize100structsqlStack intElem maxsize inttop intFact1 intn InitStack S PushStack S n while S Elem S top 1 PushStack S n 1 f 1 while EmptyStack S True f f S Elem S top PopStack S intFactorial intn if n 0 return1 returnn Factorial n 1 NorthChinaElectricPowerUniversity 4递归方程解的渐近阶的求法 解递归方程 T n 1若n 2 2T n 2 2若n 2 可以用叠代法来求解 设n 2k 且k为大于1的整数 T n 2T n 2 2 2T 2k 1 2 2 2T 2k 2 2 2 22T k 2 22 2 2k 1T 2k k 1 2k 1 2k 2 22 2 2k 1T 2 2k 2 2k 1 2k 2 3 2 2k 2 代入n 2k 得T n 3 2 n 2 NorthChinaElectricPowerUniversity 定理 设a b c是非负常数 n是c的整幂 则递归方程 T n b若n 1 aT n c bn若n 1 的解是 T n O n 若a c O nlog2n 若a c 若a c 证明 因为n是c的整幂 可得 NorthChinaElectricPowerUniversity NorthChinaElectricPowerUniversity 5生成函数 NorthChinaElectricPowerUniversity NorthChinaElectricPowerUniversity 例2求斐波那契数列的通项Fib n 的解析表达式 解设 Fib n 的生成函数为G x Fib 0 Fib 1 x Fib 2 x2 Fib n xn 1 xG x Fib 0 x Fib 1 x2 Fib 2 x3 Fib n xn 1 2 x2G x Fib 0 x2 Fib