数据结构第九章_递归ppt课件

1 第九章递归 递归的概念及设计方法递归与回朔法递归应用实例递归评价 2 若一个对象部分地包含它自己 或用它自己给自己定义 则称这个对象是递归的若一个过程直接地或间接地调用自己 则称这个过程是递归的过程 递归的定义 3 直接递归fun a fun a 递归的定义 4 4 解决问题时 可以把一个问题转化为一个新的问题 而这个新的问题的解决方法仍与原问题的解法相同 只是所处理的对象有所不同 这些被处理的对象之间是有规律的递增或递减 可以通过转化过程使问题得到简化 必定要有一个明确的结束递归的条件 否则递归将会无止境地进行下去 直到耗尽系统资源也就是说必须要某个终止递归的条件 递归条件 5 5 适用递归技术的问题 以下三种情况常常用到递归方法定义是递归的数据结构是递归的问题的解法是递归的 6 6 求解阶乘函数的递归算法longFactorial longn if n 0 return1 elsereturnn Factorial n 1 例如 阶乘函数 定义是递归的 7 例如 单链表结构 数据结构是递归的 一个结点 它的指针域为NULL 是一个单链表一个结点 它的指针域指向单链表 仍是一个单链表 8 数据结构是递归的 搜索链表最后一个结点并打印其数值voidPrint ListNode f if f link NULL printf d n f data elsePrint f link 9 问题的解法是递归的 汉诺塔 TowerofHanoi 问题的解法如果n 1 则将这一个盘子直接从A柱移到C柱上否则 执行以下三步用C柱做过渡 将A柱上的 n 1 个盘子移到B柱上将A柱上最后一个盘子直接移到C柱上用A柱做过渡 将B柱上的 n 1 个盘子移到C柱上 10 递归模型反映一个递归问题的递归结构一般地 一个递归模型是由递归出口和递归体两部分组成前者确定递归到何时为止后者确定递归的方式 递归模型 11 递归出口的一般格式为f s0 m0 这里的s0与m0均为常量 有的递归问题可能有几个递归出口递归体的一般格式为 f s g f s1 f s2 f sn c1 c2 cm s是一个递归 大问题 s1 s2 sn是递归 小问题 c1 c2 cm是若干个可以直接 用非递归方法 解决的问题g是一个非递归函数 反映了递归问题的结构 递归模型 12 例如 阶乘函数 递归出口 递归体 递归模型 13 递归的执行过程 实际上 递归是把一个不能或不好直接求解的 大问题 转化为一个或几个 小问题 来解决再把这些 小问题 进一步分解成更小的 小问题 来解决如此分解 直至每一个 小问题 都可以直接解决此时分解到递归出口 14 参数传递 结果返回 递归调用 回归求值 求解n 的过程 返回1 返回1 返回2 返回6 返回24 15 递归设计 递归设计先要给出递归模型 再转换成对应的C语言函数从递归的执行过程看 要解决f s 不是直接求其解 而是转化为计算f s 和一个常量c 求解f s 的方法与环境和求解f s 的方法与环境是相似的 但f s 是一个 大问题 而f s 是一个 较小问题 尽管f s 还未解决 但向解决目标靠近了一步 这就是一个 量变 如此到达递归出口 便发生了 质变 递归问题解决了 16 对原问题f s 进行分析 假设出合理的 较小问题 f s 假设f s 是可解的 在此基础上确定f s 的解 即给出f s 与f s 的关系 确定一个特定情况 f 1 或f 0 的解 由此作为递归出口 递归设计步骤 17 求解递归问题有两种方法直接求值不需要回溯 单向递归和尾递归 使用一些中间变量保存中间结果不能直接求值需要回溯用栈来保存中间结果 递归到非递归的转换 18 计算斐波那契数列的函数Fib n 的定义 求解斐波那契数列的递归算法 单向递归 longFib longn if n 1 returnn elsereturnFib n 1 Fib n 2 递归到非递归的转换 直接转换法 19 longFibIter longn if n 1 returnn longtwoback 0 oneback 1 Current for inti 2 i n i Current twoback oneback twoback oneback oneback Current returnCurrent 递归到非递归的转换 直接转换法 20 voidrecfunc intA intn if n 0 printf d A n n recfunc A n 尾递归 递归到非递归的转换 直接转换法 21 voidsterfunc intA intn 消除了尾递归的非递归函数while n 0 printf value d A n n 递归到非递归的转换 直接转换法 22 间接转换法一般的过程如下将初始状态s0进栈while 栈不为空 退栈 将栈顶元素赋给sif s是要找的结果 返回else 寻找到s的相关状态s1将s1进栈 递归到非递归的转换 直接转换法 23 回溯法是一个既带有系统性又带有跳跃性的的搜索算法 它在包含问题的所有解的解空间树中 按照深度优先的策略 从根结点出发搜索解空间树算法搜索至解空间树的任一结点时 总是先判断该结点是否肯定不包含问题的解如果肯定不包含 则跳过对以该结点为根的子树的系统搜索 逐层向其祖先结点回溯否则 进入该子树 继续按深度优先的策略进行搜索 回溯法 24 回溯法 回溯法在用来求问题的所有解时 要回溯到根 且根结点的所有子树都已被搜索遍才结束回溯法在用来求问题的任一解时 只要搜索到问题的一个解就可以结束 这种以深度优先的方式系统地搜索问题的解的算法称为回溯法 25 递归与回朔的区别 指导思想 回溯法是从问题的某一种可能出发 搜索从这种情况出发所能达到的所有可能当这一条路走到 尽头 的时候 再倒回出发点 从另一个可能出发 继续搜索 26 递归与回朔的区别 指导思想 递归法好比是一个军队要通过一个迷宫 3个小队沿着3条路分别前进 各自到达了路上的下一个分岔口 于是小队长再分派人手各自去探路只要人手足够 对照而言 就是计算机的堆栈足够 最后必将有人找到出口从这人开始只要层层上报直属领导 最后 将军将得到一条通路计算机的递归法是把这个并行过程串行化了 27 递归技术应用实例 汉诺塔问题 汉诺塔 TowerofHanoi 问题的解法 如果n 1 则将这一个盘子直接从A柱移到C柱上 否则 执行以下三步 用C柱做过渡 将A柱上的 n 1 个盘子移到B柱上 将A柱上最后一个盘子直接移到C柱上 用A柱做过渡 将B柱上的 n 1 个盘子移到C柱上 28 第1步是利用尾栓将N 1个盘子从头栓移到中栓第2步只需将最大的盘子从头栓移到尾栓N 1个盘子从中栓移到尾栓 用头栓作临时存放之用 汉诺塔算法 29 main intm printf Inputthenumberofdisksscanf d 8 9 30 main intm printf Inputnumberofdisks scanf d 8 9 31 main intm printf Inputthenumberofdisksscanf d 8 9 32 main intm printf Inputthenumberofdisksscanf d 8 9 33 委员会问题给出非负整数N和K 求从N个人中选出K个成员组成一个委员会的方法总数 即C N K 当数较大时 需要用 分而治之 的策略将问题分解为较简单的子问题 递归技术应用实例 组合数学 委员会问题 34 委员会问题算法 分治法 aK个成员 不包括A 的情况数加上从N 1个人中选K 1个人 包括A 的可能的情况数前一种情况的数目为C N 1 K 后一种情况下的数目为C N 1 K 1 后一种情况下 K 1个成员的委员会只要加入成员A 就可以变成K个成员的委员会 35 C N K C N 1 K 1 C N 1 K 递归步骤终止条件包括几种极端情况如果K N 那么就没有足够的人可以组成任何委员会 从N个人中选出K人委员会的情况数为0 即 C N K 0如果K 0 则委员会没有成员 这只有一种情况 即 C N 0 1如果K N 则每个成员都必须在委员会中 只有选中所有人的委员会这一种情况即 C N N 1 委员会问题算法 分治法 36 递归优点可解决复杂问题 缩短程序代码 提高编程效率递归弱点不能提高程序的运行效率 递归评价 37 计算斐波那契数列的函数Fib n 的定义 求解斐波那契数列的递归算法longFib longn if n 1 returnn elsereturnFib n 1 Fib n 2 递归程序运行效率的问题 38 调用次数Num k 2 Fib k 1 1算法复杂度为O 2n 即指数量级 斐波那契数列的递归调用树 39 longFibIter longn if n 1 returnn longtwoback 0 oneback 1 Current for inti 2 i n i Current twoback oneback twoback oneback oneback Current returnCurrent 算法复杂度为O n 斐波那契数列的迭代算法 40 为防止递归的无休止调用 在递归函数中要及时返