C++递归函数ppt课件

递归函数递归概念设计方法步骤执行过程递归与迭代典型案例 1 引例1 赏麦粒 国际象棋发明人西萨 班 达依尔在国王问赏时说 陛下 请您在这张棋盘的第1个小格里赏给我一粒麦子 在第2个小格里给2粒 第3个小格给4粒 以后每一小格都比前一小格加一倍 请您把这样摆满棋盘上所有64格的麦粒 需要多少粒麦子f 1 1 f 2 2 f 3 4 f n 2 f n 1 f 64 264 1 18446744073709551615 什么特点 2 引例2 汉诺塔问题大梵天创造世界的时候做了三根金刚石柱子 在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上 并且规定 在小圆盘上不能放大圆盘 在三根柱子之间一次只能移动一个圆盘 3 解决方法要实现将64个圆盘从第一根柱子移到第三根柱子 首先要完成将最上面的63个圆盘移到第二根柱子上 然后再将最下面的一个圆盘移到第三根柱子上 这样 如何移动64个圆盘的问题就转换成了如何移动63个圆盘问题 依次类推 解决问题的规模可以逐步降低为解决移动62 61 60 3 2 1个圆盘的问题 以上两个例子都是递归问题 4 一 递归的概念1 定义2 特点3 典型类型 5 1 定义递归方法是指通过函数或过程调用自身 将问题转化为本质相同但规模较小的子问题的方法 如果是直接调用自身 称为直接递归 如果是通过其它函数或过程间接调用自身 则称为间接递归 递归方法是算法和程序设计中的一种重要技术 是许多复杂算法的基础 A A 直接递归 间接递归 6 2 特点原始问题可转化为解决方法相同的新问题 新问题的规模比原始问题小 新问题又可转化为解决方法相同的规模更小的新问题 直至终结条件为止 7 3 典型类型 问题定义是递归的如 阶乘的定义 写成函数形式则为 这种函数定义形式是用阶乘函数自己本身定义了自身 故是一种递归定义 8 数据结构是递归的如前面介绍的链表的结点结构定义 structnode intdata structnode next 其中 指针域next是指向自身类型的指针 故该数据结构是一种递归数据结构 9 对于递归数据结构 采用递归方法编写算法简单有效 如 intsum node head if head NULL elsereturn head data 以上函数用递归算法实现了求解以head做表头指针的链表的所有结点数据的和 return0 sum head next 10 问题求解过程是递归的如 前面数组一章中介绍的在有序数组中查找某一数据是否存在于数组中的折半查找算法 其求解过程便是一个递归求解的过程 即不断在前一次区间一半的搜索区间范围内重复着与前一次搜索相同的操作 具体实现后面给出 11 二 设计方法步骤基本思想 将一复杂问题分解成若干简单且相同的子问题 这样较为复杂的原问题就转换为简单的子问题 而简单到一定程度的子问题可以直接求解 则原问题可递推得到解 递归算法所需条件 存在递归结束条件及结束时的值能用递归形式表示 且递归向终止条件发展 12 递归模型 递归模型是递归算法的抽象 反映递归问题的递归结构 以阶乘求解为例 其对应的递归模型为 fun 0 1 1 fun n n fun n 1 n 0 2 式子 1 给出了递归的终止条件 被称为递归出口 式子 2 给出了fun n 与fun n 1 之间的关系 被称为递归体 13 设计步骤 描述递归关系确定递归出口写出递归函数 intf intn if n 0 return 1 else return n f n 1 14 intfac intn if n 1 return 1 elsereturn fac n 1 n voidmain inty y f 4 cout y 为什么能计算n 考察程序执行过程 分为递推和回归两个过程 三 执行过程 返回1 返回1 2 返回1 2 3 返回1 2 3 4 15 分解 递归函数反映一种什么样的思维 问题 小问题 n n 1 问题 分解 小问题 更小问题 最小问题 分解 分解 不能再分解 n n 1 n 2 1 16 四 递归与迭代 用迭代法求n s 1 for i 1 i n i s s i 迭代过程 1 12 1 23 2 3 n n 1 n 17 1 迭代与递归的区别 迭代 自下向顶的计算过程1 12 1 23 2 3 n n 1 n递归 自顶向下逐步分解问题 最后自下向顶计算递推回归 2 迭代与递归的关系每一个递归算法总有一个迭代算法对应效率上 迭代效率高 递归低 18 五 典型案例 1 斐波那契数列700多年前 意大利有一位著名数学家斐波那契在他的 算盘全集 一书中提出了一道有趣的兔子繁殖问题 如果有一对兔子 从第三个月开始每个月都生下一对小兔 而所生下的每一对小兔在出生后的第三个月也都生下一对小兔 那么 由一对兔子开始 满一年时一共可以繁殖成多少对兔子 19 分析 第一 二个月都只有一对兔子 到第三个月第一对兔子生一对小兔 则该月共有2对 1 1 2 兔子 第四个月 第一对兔子又生了一对兔子 因此共有3对 1 2 3 兔子 到第五个月 第一对兔子又生了一对小兔而在第三个月出生的小兔也生下了一对小兔 所以 这个月共有5对 2 3 5 兔子 规律 从三月份开始兔子总对数 恰好等于前面两个月份兔子总对数的和 因为该月的兔子对总数应该等于上个月的兔子对数加上新出生的小兔对数 而新出生的小兔对数恰好为上上个月的兔子对数 因上上个月的每对兔子到该月都会生出一对新兔子 20 于是得到每个月的兔子对数 1 1 2 3 5 8 13 21 34 55 89 144 233 377 人们为了纪念这位数学家 就把上面这样的一串数称作斐波那契数列 把这个数列中的每一项数称作斐波那契数 斐波那契数列的递归定义 21 f 1 1 f 2 1f n f n 1 f n 2 问题 子问题1 子问题2 与 f n f n 1 f n 2 intfib intn if return 1 else 与的关系 子问题解决了 大问题就解决了 递归出口 递归体 n 1 n 2 return fib n 1 fib n 2 22 2 猴子吃桃子小猴在一天摘了若干桃 当天吃掉一半多一个 第二天接着吃掉剩下的一半多一个 以后每天都吃掉尚存桃子的一半多一个 第7天早上只剩1个 问小猴摘了多少个桃 分析 由题意知 第n天的桃子个数应是第n 1天个数加1以后的2倍 故可归纳出 递归体 f n f n 1 1 2递归出口 f 7 1 23 intf intn else 递归函数定义如下 if n 7 return1 return f n 1 1 2 24 3 十进制整数转换成二至九任意进制数 voidf intn intr if n 0 f n r r cout n r 调用输出f 100 8 4f 12 8 4f 1 8 1f 0 8 递归出口为n 0 最先分解出的最后输出 若转换成2 16进制呢 voidf intn intr if n 0 return else f n r r cout n r 或 25 4 二分法查找的递归实现 在low和high之间查找 在low和mid 1之间查找 在mid 1和high之间查找 结果是a mid intBinary Search intlow inthigh if return 1 intmid low high 2 if key a mid returnmid elseif key a mid else low high returnBinary Search low mid 1 returnBinary Search mid 1 high 26 5汉诺塔问题有A B和C三根柱子 A上从上到下按照从小到大的顺序摞着n个圆盘 要求借助B从A上将n个圆盘移到C上 移动规定 一次只能移动1个圆盘 小圆盘上不能放大圆盘递归分析 借助C从A上将n 1个圆盘移到B上 从A上将1个圆盘移到C上 借助A从B上将n 1个圆盘移到C上 27 大问题 hanoi n A B C 子问题1 子问题2 子问题3 将n个盘从one座借助two座 移到three座 voidhanoi intn charone chartwo charthree hanoi n 1 A C B move A C hanoi n 1 B A C 28 include iostream h voidmain voidhanoi intn charone chartwo charthree intm cin m hanoi m A B C voidhanoi intn charone chartwo charthree voidmove charx chary if n 1 move one three else hanoi n 1 one three two move one three hanoi n 1 two one three voidmove charx chary cout y endl 29 6 分形图形 从一个大的等边三角形开始 将其三条边的中点进行连线 分成相等的4个三角形 除中间外的3个三角形再重复上述过程 直到满足规定的条件的底层 不做要求 仅供参考 30 x y 三角形中心点坐标 x1 y1 x2 y2 x3 y3 三角形三个顶点的坐标 x01 y01 x02 y02 x03 y03 分别代表三个小三角形中心点坐标 31 include graphics h include conio h include iostream h include math h definePI3 14voiddrawpic doublex doubley doublelen intk voidmain intn cin n 递归深度initgraph 600 600 初始化屏幕大小600 600drawpic 300 300 500 n getch closegraph 三角形中心点坐标 边长 递归深度 32 voiddrawpic doublex doubley doublelen intk doublex1 y1 x2 y2 x3 y3 x01 y01 x02 y02 x03 y03 if k 1 x1 x len 2 y1 y len 2 tan PI 6 x2 x len 2 y2 y len 2 tan PI 6 x3 x y3 y len tan PI 6 line x1 y1 x2 y2 line x2 y2 x3 y3 line x3 y3 x1 y1 else x01 x len 4 y01 y len tan PI 6 4 x02 x len 4 y02 y len tan PI 6 4 x03 x y03 y len tan PI 6 2 drawpic x01 y01 len 2 k 1 drawpic x02 y02 len 2 k 1 drawpic x03 y03 len 2 k 1 递归出口 33