第6章 递归和广义表.ppt

第6章递归和广义表 DataStructures WuhanUniversity 2 本章内容 递归广义表 略 DataStructures WuhanUniversity 3 WuhanUniversity 递归 什么是递归 何时使用递归 DataStructures WuhanUniversity 什么是递归 从前有座山山上有座庙的故事 一个事件或对象 部分的由自己组成 或者用它自己来定义 则称这个对象是递归的 例如 用递归来定义偶数 1 一个偶数加上2还是偶数 2 0是偶数 DataStructures WuhanUniversity 递归函数 又称为自调用函数 即自己调用自己的函数 函数直接或间接调用自己的算法称为递归算法 分类 直接递归 函数直接调用本身 A CALLA 间接递归 函数在调用其他函数时 产生了对自身的调用 A B CALLB CALLA DataStructures WuhanUniversity 递归函数 例 以下是求n n为正整数 的递归函数 intfun intn intx if n 1 递归出口 x 1 elsex fun n 1 n 递归体 return x 在该函数fun n 求解过程中 直接调用fun n 1 自身 所以它是一个直接递归函数 DataStructures WuhanUniversity 递归算法 递归算法包括两部分 递推 递归体 为得到问题的解 将其推导到比原来问题更为简单的问题求解上 回归 递归出口 简单问题得到解后 回归到原问题的解上 递归算法的思路 把一个不能或不好直接求解的 大问题 转化成一个或几个 小问题 来解决 再把这些 小问题 进一步分解成更小的 小问题 来解决 如此分解 直至每个 小问题 都可以直接解决 即分解到递归出口 但递归分解不是随意的分解 递归分解要保证 大问题 与 小问题 相似 即求解过程与环境都相似 DataStructures WuhanUniversity 递归算法 采用递归算法需具备的条件 要解决的问题可以转化成另一个问题 解决新问题的方法与原始问题的解决方法相同 必须具备终止递归的条件 DataStructures WuhanUniversity 何时使用递归 在以下三种情况下 常常要用到递归的方法 定义是递归的数据结构是递归的问题的求解方法是递归的 DataStructures WuhanUniversity 定义是递归的 有许多数学公式 数列等的定义是递归的 例如 求n 和Fibonacci数列等 这些问题的求解过程可以将其递归定义直接转化为对应的递归算法 intFib intn intx if n 1 n 2 x 1 递归出口 elsex Fib n 1 Fib n 2 递归体 returnx DataStructures WuhanUniversity 数据结构是递归的 有些数据结构是递归的 例如 第2章中介绍过的单链表就是一种递归数据结构 其结点类型定义如下 typedefstructLNode ElemTypedata 数据域 structLNode next 指针域 LinkList 该定义中 结构体LNode的定义中用到了它自身 即指针域next是一种指向自身类型的指针 所以它是一种递归数据结构 DataStructures WuhanUniversity 数据结构是递归的 对于递归数据结构 采用递归的方法编写算法既方便又有效 例如 求一个不带头结点的单链表head的所有data域 假设为int型 之和的递归算法如下 intSum LinkList head if head NULL 递归出口 return0 else 递归体 return head data Sum head next DataStructures WuhanUniversity 问题的求解方法是递归的 有些问题的求解方法是递归的例如汉诺塔 Hanoi 问题八皇后问题 DataStructures WuhanUniversity 汉诺塔问题 问题描述 有三个命名为A B C的塔座 在塔座A上插有n个直径各不相同的 从小到大依次编号为1 2 3 n的圆盘 编号越大的圆盘其直径越大 要求将A轴上的n个圆盘全部移至塔座C上并仍按同样顺序叠放 并且圆盘移动时必须遵循下列规则 每次只能移动一个圆盘 圆盘可以插入A B C中任一个塔座上 任何时候都不能将一个较大的圆盘压在较小的圆盘上 DataStructures WuhanUniversity 汉诺塔问题 n 3 DataStructures WuhanUniversity 汉诺塔问题 n 6 DataStructures WuhanUniversity 汉诺塔问题 递归算法分析 对于n 1的问题 可以分解为下列三个子问题将塔座A顶端n 1个圆盘通过塔座C移动到塔座B将塔座A最后一个圆盘移动到塔座C 即A C将塔座B顶端n 1个圆盘通过塔座A移动到塔座Cn 1时 问题可直接求解 将塔座A的圆盘移动到塔座C 即A C所以整个过程分成如下两类操作将N 1个盘子从一个塔座移到另一个塔座上 这是一个递归过程将1个盘子从一个塔座移到另一塔座上 DataStructures WuhanUniversity 汉诺塔问题 递归算法实现 voidmove charx chary 把盘子从x移动到y printf c c n x y voidhanoi intn charx chary charz 递归算法 if n 1 move x z else hanoi n 1 x z y 把n 1个盘子从x借助z移到ymove x z 把盘子n从x直接移到zhanoi n 1 y x z 把n 1个盘子从y借助x移到z DataStructures WuhanUniversity 八皇后问题 问题描述 在一个8 8的棋盘上放置8个皇后 那么n个皇后的问题就是在n n的棋盘上放置n个皇后 规则 不允许两个皇后在同一行 同一列或同一对角线上 图示 DataStructures WuhanUniversity 八皇后问题 实例 四皇后问题 DataStructures WuhanUniversity 八皇后问题算法分析 回溯法 与求解迷宫问题类似 从第一行开始尝试在棋盘上摆放皇后 每行只能放一个皇后 若找到一个合法位置 则尝试在下一行摆放下一个皇后 若发现某行皇后无位置可放 则返回上一行 尝试其他位置 重复此过程 可找到所有解 DataStructures WuhanUniversity 八皇后问题算法分析 如何判断棋盘上某个位置是否能摆放新的皇后 测试皇后间位置冲突 行 列 对角线行 规定每行只放一个皇后 不会发生冲突 列 当第i列已被某个皇后占领后 则同列上不能再放其他皇后 对角线 DataStructures WuhanUniversity 八皇后问题算法分析 等腰三角形 第j行 第i列 第x行 queen j 第x行第i列上是否能摆放皇后 前x 1行都已摆放好 每行皇后列号保存在数组queen中 queen j i abs queen j i abs j x 列冲突 对角线冲突 DataStructures WuhanUniversity 八皇后问题算法实现 测试第x行第i列上是否能摆放皇后 intsearch intx inti intj 行号 j 0 while j x queen j 第j行皇后摆放的列坐标位置 if queen j i abs queen j i abs j x return0 j return1 DataStructures WuhanUniversity 八皇后问题算法实现 续 voidplace queen intq intn 第q个皇后放到第q行上 inti j i 0 总共有n个皇后 while i n i为列号 if search q i 第q行第i列可以摆放皇后 queen q i 将列号保存到数组queen的第q个元素中 if q n 1 若n个皇后均已放好 则输出每个皇后所在行列数 count printf 第 d个解 count for j 0 j n j printf d d j 1 queen j 1 printf n elseplace queen q 1 n 否则摆放下一个皇后 递归 i 从第一行开始调用此函数 即可找到所有解 DataStructures WuhanUniversity 迷宫问题也可用递归算法解决 DataStructures WuhanUniversity 本章学习要点 理解递归的定义和递归的执