递归与广义表.ppt

递归 Recurve 的概念 迷宫 Maze 问题 递归过程与递归工作栈 小结 递归的概念 递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的 定义是递归的 求解阶乘 n! 的过程  在链表中寻找等于给定值的结点并打印其数值template void Print ListNode *f, Type x  if f ! NULL  if f →data x  cout f→data endl; else Print f→link, x ; 迷宫问题 Maze :: Maze char *filename //构造函数：从文件 filename 中读取各路口//和出口的数据 ifstream fin; fin.open filename, ios::in | ios::nocreate ; //为输入打开文件,文件不存在则打开失败 if !fin  cout “迷宫数据文件” filename  “打不开” endl; exit 1 ;  fin MazeSize; //输入迷宫路口数 递归过程与递归工作栈 递归过程在实现时，需要自己调用自己。 每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。 层层向下递归，退出时的次序正好相反： 递归次序 n! n-1 ! n-2 ! 1! 0! 1 返回次序 因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。 函数递归时的活动记录 递归举例 【例1】求解斐波那契数列的递归算法 long Fib long n  if n 1 return n;  else return Fib n-1 + Fib n-2 ;  考虑使用递归算法求解的思路 递归算法的一般形式 void p 参数表 if 递归结束条件 可直接求解步骤； 基本项 else p 较小的参数 ; 递归项 【例2】求数组 A 中 n 个整数的和 int sum int n int result; if n 1 result A[0]; else result A[n-1] + sum n-1 ; return result; 递归与回溯 常用于有哪些信誉好的足球投注网站过程 【例3】n皇后问题 在 n 行 n 列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局。 解题思路 安放第 i 行皇后时，需要在列的方向从 1 到 n 试探 j 1, …, n 在第 j 列安放一个皇后： 如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第 j 列安放的皇后。 如果没有出现攻击，在第 j 列安放的皇后不动，递归安放第 i+1行皇后。 设置 4 个数组 col [n] ：col[i] 标识第 i 列是否安放了皇后 md[2n-1] : md[k] 标识第 k 条主对角线是否安放了皇后 sd[2n-1] : sd[k] 标识第 k 条次对角线是否安放了皇后 q[n] : q[i] 记录第 i 行皇后在第几列 void Queen int i for int j 1; j n; j++ if 第 i 行第 j 列没有攻击 在第 i 行第 j 列安放皇后； if i n 输出一个布局； else Queen i+1 ; 撤消第 i 行第 j 列的皇