《《递归算法梁》PPT课件》由会员分享，可在线阅读，更多相关《《递归算法梁》PPT课件（30页珍藏版）》请在装配图网上搜索。
1、主 讲 ： 梁 宝 兰 2 主 要 内 容 ：递 归 的 概 念递 归 算 法 的 执 行 过 程递 归 算 法 的 设 计 方 法递 归 过 程 和 运 行 时 栈递 归 算 法 的 效 率 分 析递 归 算 法 到 非 递 归 算 法 的 转 换 3 递 归 算 法 直 接 或 间 接 调 用 自 身 的 算 法 称 为 递 归 算 法1、 问 题 的 定 义 是 递 归 的 例 ： 阶 乘 函 数 定 义 时当 时当 0n )!1(* 0n 1! nnn 4 2、 问 题 的 解 法 存 在 自 调 用例 ： 在 有 序 数 组 a中 查 找 是 否 存 在 元 素 x。二 分 查 找
2、思 想 ：在 alowahight(low为 寻 找 区 域 中 开 始 处 下 标 ， high则 为 结 束 处 的 下 标 )寻 找 是 否 存 在 元 素 x；若 lowhigh,则 不 存 在 x， 返 回 -1；否 则 ， 求 出 中 间 元 素 下 标 mid=(low+high)/2；若 amid=x ， 则 查 找 成 功 返 回 mid的 值 ；若 amidx则 在 alowamid-1间 继 续 寻 找 ；若 amid21;则 high=mid-1=4， 并 在 alowahigh中 继 续 查 找 ；第 二 次 比 较 ： low=0， high=4， mid=2； a
3、mid20;则 high=mid-1=4， 并 在 alowahigh中 继 续 查 找 ；第 二 次 比 较 ： low=0， high=4， mid=2； amid20;则high=mid-1=2， 并 在 alowahigh中 继 续 查 找 ；第 四 次 比 较 ： lowhigh, 20不 存 在 数 组 中 ， 返 回 -1； 7 /算 法 实 现int bin_search (node r ,int low,int high,ElemType k) int mid; if(lowk) return bin_search (r,low,mid-1,k); /左 else retur
4、n bin_search (r, mid-1,high,k); /右 8 /求 阶 乘 的 递 归 程 序int fact(int n) int x,y; if (n0) cout“error!”endl; return -1; if(n=0) return 1; else x=n-1; y=fact(x); return n*y; void main() int fn; fn=fact(3); coutfnmn; cout路 径 总 数 ： road(m,n);endl; 18 递 归 算 法 的 优 点 ： 结 构 清 晰 ， 可 读 性 强 ， 容 易 用 数 学 归 纳 法来 证 明
5、算 法 的 正 确 性 。递 归 算 法 的 缺 点 ： 递 归 算 法 ， 需 要 多 次 调 用 自 身 ， 在 调 用 函数 时 ， 现 场 保 护 以 及 恢 复 现 场 消 耗 时 间 与 空 间 ；且 递 归 算 法 ， 往 往 不 能 利 用 已 经 求 解 过 得 问 题的 解 ， 导 致 重 复 计 算 ， 消 耗 时 间 。 19 递 归 算 法 转 化 为 非 递 归 算 法 有 两 种 基 本 方 法 ：1、 可 用 循 环 结 构 进 行 递 推 。2、 自 己 用 堆 栈 模 拟 系 统 的 运 行 时 的 栈 ， 通 过 分析 只 保 存 必 须 保 存 的 信
6、息 ， 从 而 用 非 递 归 算 法替 代 递 归 算 法 (略 ) 。 20 如 ： 阶 乘 问 题 的 递 归 算 法 Fact(n) long fact2(int n) int fac=1; for(inti=1;i=n;i+) fac=fac*i; return fac; long fact1(int n) if(n=0) return 1; return n*fact1(n-1); 21 /二 分 查 找 法 算 法 的 非 递 归 实 现int bin_search (int a ,int low,int high,int k) int mid; while(lowk) hig=
7、mid-1; /在 左 子 区 间 中 查 找 else low=mid+1; /在 右 子 区 间 中 查 找 return(-1); 22 /利 用 二 维 数 组 进 行 递 推 求 解 田 字 表 中 路 径 数 函 数int road (int m,int n) int rMaxMMaxN,count=0; for(int x=0;x=m;x+) rx0=1; for(int y=0;y=n;y+) r0y=1; for( x=1;x=m;x+) for( y=1;y=n;y+) rxy=rx-1y+rxy-1; return rmn; 23 6.7.1 一 般 递 归 算 法 设
8、计 举 例 例 6-5 设 计 一 个 输 出 如 下 形 式 数 值 的 递 归 算 法 。n n n . n. 3 3 3 2 21问 题 分 析 ： 该 问 题 可 以 看 成 由 两 部 分 组 成 ： 一 部 分 是输 出 一 行 值 为 n的 数 值 ； 另 一 部 分 是 原 问 题 的 子 问 题 ，其 参 数 为 n-1。 当 参 数 减 到 0时 不 再 输 出 任 何 数 据 值 ，因 此 递 归 的 出 口 是 当 参 数 n0时 空 语 句 返 回 。 24 /算 法 设 计 ： 递 归 算 法 设 计 如 下 ：void Display(int n) int i;
9、for(i = 1; i = n; i+) coutsetw(5)n; cout 0) Display(n - 1); /递 归 ， n1且 nk,则 P(1)要 么 在 委 员 会 中 ， 要 么 不 在 ，则 ；当 P(1)在 委 员 中 时 ， 则 需 要 在 P(2)P(n)中 选 举 k-1个 人当 P(1)在 委 员 中 时 ， 则 需 要 在 P(2)P(n)中 选 举 k个 人 26 27 /委 员 会 选 举 函 数int comm(n,k)/在 n个 人 种 选 举 k个 委 员 的 方 法 数 if (n=k|k=0) return 1; else return comn(n-1,k-1)+comnn(n-1,k); 28 作 业 9 10 11 12（ 1） 29 利 用 非 递 归 算 法 求 解 委 员 会 选 举 问 题 。
《递归算法梁》PPT课件
