《【数据结构英文课件】recursion》由会员分享，可在线阅读，更多相关《【数据结构英文课件】recursion（32页珍藏版）》请在金锄头文库上搜索。
1、 Chapter 5 RECURSION 1. Introduction to Recursion 2. Principles of Recursion 3. Backtracking: Postponing the Work 4. Tree-Structured Programs: Look-Ahead in Games 5. Pointers and Pitfalls 5.1 Stacks and Trees 数据结构是递归的 THEOREM 5.1 During the traversal of any tree, vertices are added to or deleted fro
2、m the path back to the root in the fashion of a stack. Given any stack, conversely, a tree can be drawn to portray the life history of the stack, as items are pushed onto or popped from it. Tree-Diagram Definitions The circles in a tree diagram are called vertices or nodes. The top of the tree is ca
3、lled its root. The vertices immediately below a given vertex are called the children of that vertex. The (unique) vertex immediately above a given vertex is called its parent. (The root is the only vertex in the tree that has no parent.) The line connecting a vertex with one immediately above or bel
4、ow is called a branch. Siblings are vertices with the same parent. 分支 兄弟 A vertex with no children is called a leaf or an external vertex. Two branches of a tree are adjacent if the lower vertex of the first branch is the upper vertex of the second. A sequence of branches in which each is adjacent t
5、o its successor is called a path. The height of a tree is the number of vertices on a longest possible path from the root to a leaf. (Hence a tree containing only one vertex has height 1.) The depth or level of a vertex is the number of branches on a path from the root to the vertex. Factorials: A R
6、ecursive Definition Informal definition: The factorial function of a positive integer is n! = n(n-1)1 Formal definition: 定义是递归的 Every recursive process consists of two parts: A smallest, base case that is processed without recursion; and A general method that reduces a particular case to one or more
7、 of the smaller cases, thereby making progress toward eventually reducing the problem all the way to the base case. boundary recursion Towers of Hanoi Rules: Move only one disk at a time. No larger disk can be on top of a smaller disk. 问题的解法是递归的 void move(int count, int start, int finish, int temp);
8、 /* Pre: There are at least count disks on the tower start. The top disk (if any) on each of towers temp and finish is larger than any of the top count disks on tower start. Post: The top count disks on start have been moved to finish; temp (used for temporary storage) has been returned to its start
9、ing position.*/ const int disks = 64; / Make this constant much smaller to run program. void move(int count, int start, int finish, int temp); /* Pre: None. Post: The simulation of the Towers of Hanoi has terminated. */ main( ) move(disks, 1, 3, 2); void move(int count, int start, int nish, int temp
10、) if (count 0) move(count - 1, start, temp, nish); cout Move disk count from start to finish . 0) / Replace theif statement with a loop. move(count - 1, start, temp, finish); / first recursive call cout Move disk count from start to finish . endl; count-; / Change parameters to mimic the second recu
11、rsive call. swap = start; start = temp; temp = swap; Calculating Factorials Please see pg. 176-177 Fibonacci Numbers Please see pg. 177-179 5.3 Backtracking Eight Queens Puzzle Four Queens Solution Please see pg.184 fig.5.13 回溯法也称为 状态空间搜索法， 用它可以求出 问题的所有解。 在8*8的国际象棋上 摆放八个皇后，使其 不能互相攻击,即任意 两个皇后不能处于同一行、
12、 同一列或同一斜线上， 问有多少种摆法。 Solve the problem using recursive : #include #include # define max_board 30 int sum=0; / 计数所得解数目 int xmax_board; / 存放当前解的向量 int board_size; / 皇后个数 ofstream out(“Queen.out”); / 声明并且打开输出文件流 void Backtrack(int); / 递归回溯法 递归求解 void main(void) cout board_size; if (board_sizemax_board)
13、 coutThe number must be between 0 and max_boardendl; else Backtrack(0); outnThe number of solution Queen is sumendl; out.close(); bool Place(int k) / 检测k皇后能否放在xk列 for(int j=0; jk; j+) if(abs(k-j)=abs(xj-xk) | xj=xk) return false; return true; void Backtrack(int i) / 递归回溯法 int j; if(i=board_size) /找到
14、一组解，输出 sum+; for(j=0; jboard_size; j+)out xj; outendl; for(j=0; jboard_size; j+) / xi=j; if(Place(i)Backtrack(i+1); /确定位置，找下一皇后位置 Queens Solution (book) Please see pg.186 - pg.194 Please with the top of solution method compare Solve the problem using iterate: 迭代求解 void main() cout board_size; if(board_sizemax_board) coutThe number must be between 0 and max_board=0 ) / 若k0，则已搜索完所有的解, 结束回溯 xk+; while(xkboard_size) if(xkboard_size) / 确定了皇后的位置 if(k=board_size-1) /找到一组解，输出 sum+; for(int i=0; iboard_size; i+)out xi; out
