C语言程序设计尹宝林.pps

C语言程序设计 尹宝林 第四讲：递归 2005-1-21C语言程序设计进阶 递归的概念和作用 n概念或函数直接或间接引用自身 n在可计算性理论中有重要的地位 n递归可枚举 n常用的重要机制 n概念的表达 n数据结构和算法的描述 n重要的思维方式 n现代程序设计语言中都提供支持 2005-1-22C语言程序设计进阶 递归概念的例 n树 n树的非递归定义 n连通且无圈的无向图 n树的递归定义 n一个节点是一棵树 n一棵树的每个节点可以有m个分支 ，其中每一个分支都是一棵树 n一棵树中的任意两个节点间只有一 条通路 2005-1-23C语言程序设计进阶 递归算法的例 n排序 n归并排序(merge sort) n最典型常用的实现方法是通过递归 的定义 n快速排序算法(quick sort) n直接通过递归定义 2005-1-24C语言程序设计进阶 递归函数的例 n直接引用的递归函数：对树的中序遍历 typedef struct t_node int value; struct t_node *l_tree, *r_tree; t_node; void treat_tree(t_node *treep, void (*op_func)(int) if (treep = NULL) return; treat_tree(treep-l_tree, op_func); op_func(treep-value); treat_tree(treep-r_tree, op_func); 2005-1-25C语言程序设计进阶 递归函数的例(续) n间接引用的递归函数 void a(int i) b(i 1); void b(int i) a(i); 2005-1-26C语言程序设计进阶 递归函数的例(续) n递归曲线 nHilbert曲线 nSierpinski曲线 n分形（fractal） 2005-1-27C语言程序设计进阶 递归在程序设计中的例 n程序设计语言的语法描述 nBackus-Naur Form (巴克斯范式） nAlgol、C、 n数据结构 n控件 n复杂的嵌套结构 n 2005-1-28C语言程序设计进阶 递归的优点 n概念清晰，易于理解 n描述简单，易于实现 n例：GUI中的嵌套的选单(Menu) n代码紧凑，易于维护 2005-1-29C语言程序设计进阶 递归函数的缺点 n在某些情况下计算复杂度较高 n不适当的定义引起的重复计算 n在某些情况下占用存储空间较多 n深度递归调用引起的资源消耗 n函数调用的开销 n计算过程简单时函数调用开销的比例增 加 2005-1-210C语言程序设计进阶 理解和使用递归的难点 n递归的基本思维方法 n递归概念的表示 n使用递归方法求解问题 n递归过程的描述方法 n递归的执行过程 n递归的使用条件和环境 n在什么情况下应该使用递归 2005-1-211C语言程序设计进阶 递归概念的表示 n自引用结构 n例1：二叉树的表示 typedef struct tree_node int value; struct tree_node *l_tree; struct tree_node *r_tree; tree_node; n例2：单向链表的表示 typedef struct list int value; struct list *next; list; 2005-1-212C语言程序设计进阶 递归过程描述的基本思想 n把问题化为形式相同但规模较小的问题 n在问题规模缩小到一定的程度时加以解 决 n递归的描述 n定义对问题可以直接求解的情况和方法 n用自引用的方式描述问题的一般求解过程 n在对自身的引用过程中降低问题的复杂度 n在复杂度降低到一定程度时直接求解 2005-1-213C语言程序设计进阶 递归过程描述的基本思想(续) n与数学归纳法类似 n数学归纳法 在证明一个关于整数的公式时 n证明该公式对一个整数k成立 n假设该公式对某一整数n成立 n证明该公式对整数n+1成立 2005-1-214C语言程序设计进阶 递归过程的描述步骤 n确定递归参数 n定义递归的终止条件和基础计算 n当递归参数为一个确定的值时应当如何 直接进行计算 n定义递归调用 n当递归参数不满足终止条件时，将计算 表示为包含对自身调用的计算 n对自身调用时递归参数应更接近终止条 件 2005-1-215C语言程序设计进阶 递归过程描述的例 n阶乘 0! = 1 n! = n * (n 1)! n组合公式 Cm1 = m Cmm = 1 Cmn = Cnm-1 + Cn-1 m-1 2005-1-216C语言程序设计进阶 递归过程描述的例(续) n梵塔 n初始状态： nN个(N 0)大小不同的圆盘插在柱A上，大盘 在下，小盘在上。柱B和柱C上为空 n任务： n将所有的圆盘移到柱B上，仍保持大盘在 下，小盘在上的状态 n限制条件： n每次只能移动一个盘 n可以把圆盘临时放在任一柱上，但大盘不 能压住小盘 2005-1-217C语言程序设计进阶 递归过程描述的例(续) n梵塔问题递归求解的思路 n当n等于1时 n直接将盘由柱A移至柱B n当n大于1时 将顶部的n 1个盘由柱A移至柱C 将底部的大盘由柱A移至柱B 将柱C上的n 1个盘移至柱B 2005-1-218C语言程序设计进阶 递归函数的基本结构 n基础计算 n递归的基础条件(终止条件) n递归的基础计算 n递归调用 n直接或间接的对自身的引用 n对递归控制参数的修改 n向着递归终止条件方向变化 n递归调用时的其它计算 2005-1-219C语言程序设计进阶 n计算 n 的阶乘 int factorial(int n) if (n = 0) return 1; return n * factorial(n 1); n计算组合公式 int comb_num(int m, int n) if (m #include #define MAXNUM 16 int main(int c, char* v) int rMAXNUM, i, n; n = atoi(v1); for (i = 0; i 4 2 3 1 5 - 4 1 2 3 5 1 2 3 4 5 - 5 2 3 4 1 - 5 1 2 3 4 n缺点：思路稍微复杂一些 n优点 n实现简单，便于恢复原状，不需单独存储 n对原算法影响小 2005-1-235C语言程序设计进阶 排序版本的permu()： void permu(int *r, int k, int m) int i; if (k = m) output(r, m); return; for(i = k; i = right) return; tmp = rright; for (i = right; i left; i-) ri = ri - 1; rleft = tmp; void circular_left(int *r, int left, int right) . . 2005-1-237C语言程序设计进阶 错误处理： int main(int c, char* v) int rMAXNUM, i, n; if (c != 2) fprintf(stderr, “Usage: %s Nn“, v0); exit(1); n = atoi(v1); if (n MAXNUM) fprintf(stderr, “N must be between 2 and %dn“, MAXNUM); exit(2); for (i = 0; i = 0; i-) if (ai = x) return i; return 0; n顺序查找函数的递归定义 int r_search(int a, int n, int x) if (an = x) return n; return r_search(a, n - 1, x); 2005-1-245C语言程序设计进阶 顺序查找的算法效率比较 数据项数 200500100020005000 s_search (mS) 0.0020.0050.0130.0220.048 r_search (mS) 0.0920.2550.5561.163.01 2005-1-246C语言程序设计进阶 重复计算的例：斐波纳契函数 n斐波纳契函数的递归定义 n斐波纳契函数 F(0) = 1; F(1) = 1; F(n) = F(n 1) + F(n 2) n斐波纳契函数的C代码 fib(int n) if (n = 0 | n = 1) return 1; return fib(n 1) + fib(n 2); 2005-1-247C语言程序设计进阶 例：斐波纳契函数(续) n斐波纳契函数的执行 n一个值会被多次使用 n例： F(10)-F(9)-F(8) F(9)-F(8)-F(7) n任何已被计算过的值都不会被保留 n一个值会被多次重复计算 2005-1-248C语言程序设计进阶 例：斐波纳契函数(续) n斐波纳契函数的效率 n调用次数与参数的关系 参数5101520253035 调用次数 15177197321891242785269253729860703 2005-1-249C语言程序设计进阶 递归函数效率的改进 n避免不必要的重复计算 n保存已经计算过的值 n例：斐波纳契函数的改进 n函数的非递归化 n尾递归函数 n简单递归函数 2005-1-250C语言程序设计进阶 尾递归函数的非递归化 n尾递归(tail recursion) n递归调用位于函数的最末尾 n在递归调用返回后无其它操作 n尾递归的非递归化 n直接转换成循环 n节省存储空间 n避免调用和函数栈 n时间效率有改进 n编译系统可自动优化 n例：顺序查找的递归定义在编译的优化时 被消除 2005-1-251C语言程序设计进阶 尾递归优化的例 n例：阶乘的非递归算法 F(1) = 1, F(n) = n * F(n 1) int factorial(int n) int i, f = 1; for (i = 1; i value) return max_list(list-next, lst-value); else return max_list(lst-next, max_so_far); 2005-1-253C语言程序设计进阶 n求链表中最大值的非递归算法 int max_list(list *lst, int max_so_far) for (;) if (null = lst) return max_so_far; if (max_so_far value) max_so_far = lst-value; lst = lst-next; 2005-1-254C语言程序设计进阶 简单递归函数的非递归化 n不需要回溯 n有重复计算 n解决方法 n可以使用变量保存中间结果，直接计算 n一般可以显著提高效率 n一般过程 n从基础条件处开始计算 n使用循环语句进行控制 2005-1-255C语言程序设计进阶 简单递归函数非递归化的例 n例：斐波纳契函数的非递归算法 int fib(int n) int i, fMAX_ITEM; if (n = 0 | n = 1) return 1; f0 = f1 = 1; for (i = 2; i 0 int stMAX_DEPTH; ack(int x, int y) int n = 0; push(x), push(y); while (not_empty) pop(y), pop(x); if (x = 0) push(y + 1); else if (y = 0) push(x - 1); push(1); else push(x - 1); push(x); push(y - 1); return st0; 2005-1-259C语言程序设计进阶 n阿克曼函数的非递归化(2) n减少栈操作次数 #define not_empty n = 0 ack(int x, int y) int n = 0; do if (x = 0) pop(x), y += 1; else if (y = 0) x -= 1; y = 1; else push(x - 1); y -= 1; while (not_empty); return y; 2005-1-260C语言程序设计进阶 递归函数非