3_2递归与非递归.ppt

北京化工大学信息学院 数据结构 递归的概念 递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的 * 北京化工大学信息学院 数据结构 * 定义是递归的 求解阶乘函数的递归算法 long Factorial ( long n ) { if ( n == 0 ) return 1; else return n * Factorial (n-1); } 例如，阶乘函数 * 北京化工大学信息学院 数据结构 * 求解阶乘 n! 的过程 主程序 main : fact(4) 参数 4 计算 4*fact(3) 返回 24 参数 3 计算 3*fact(2) 返回 6 参数 2 计算 2*fact(1) 返回 2 参数 1 计算 1*fact(0) 返回 1 参数 0 直接定值 = 1 返回 1 参数传递 递归调用 结果返回 回归求值 * 北京化工大学信息学院 数据结构 * 数据结构是递归的 一个结点，它的指针域为NULL，是一个单链表; 一个结点，它的指针域指向单链表，仍是一个单链表。 例如，单链表结构 f ? f ? * 北京化工大学信息学院 数据结构 * void Print ( ListNode *f ) { if ( f -link == NULL ) printf (“%d\n”, f -data ); else Print ( f -link ); } f f f f f ? a0 a1 a2 a3 a4 递归找链尾 有哪些信誉好的足球投注网站链表最后一个结点并打印其数值 * 北京化工大学信息学院 数据结构 * 在链表中寻找等于给定值的结点并打印其数值void Print ( ListNode *f, ListData x ) { if ( f != NULL ) if ( f - data == x ) printf (“%d\n”, f -data ); else Print ( f - link, x );} f f f f ? 递归找含x值的结点 x * 北京化工大学信息学院 数据结构 * 例如，汉诺塔(Tower of Hanoi)问题的解法： 如果 n = 1，则将这一个盘子直接从 A 柱移到 C 柱上。否则，执行以下三步： ① 用 C 柱做过渡，将 A 柱上的 (n-1) 个盘子移到 B 柱上： ② 将 A 柱上最后一个盘子直接移到 C 柱上； ③ 用 A 柱做过渡，将 B 柱上的 (n-1) 个盘子移到 C 柱上。 问题的解法是递归的 * 北京化工大学信息学院 数据结构 * * 北京化工大学信息学院 数据结构 * 汉诺塔问题 * 北京化工大学信息学院 数据结构 * 自顶向下、逐步分解的策略 子问题应与原问题做同样的事情，且更为简单； 解决递归问题的策略是把一个规模比较大的问题分解为一个或若干规模比较小的问题，分别对这些比较小的问题求解，再综合它们的结果，从而得到原问题的解。 —分而治之策略（分治法） 这些比较小的问题的求解方法与原来问题的求解方法一样。 * 北京化工大学信息学院 数据结构 * 构成递归的条件 递归三要素 1、问题的形式 2、递归的规则 3、终结条件 long FN( long N ) return N * FN(N-1); if( N=1 ) return 1; * 北京化工大学信息学院 数据结构 * 递归过程与递归工作栈 递归过程在实现时，需要自己调用自己。 层层向下递归，退出时的次序正好相反： 递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序 主程序第一次调用递归过程为外部调用； 递归过程每次递归调用自己为内部调用。 它们返回调用它的过程的地址不同。 * 北京化工大学信息学院 数据结构 * 递归工作栈 每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。 每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。 局部变量 返回地址 参 数 活动记录框架 递归 工作记录 * 北京化工大学信息学院 数据结构 * 函数递归时的