Chapter 5 RECURSION I1. Introduction to Recursion 2. Principles of Recursion L3 Backtracking: Postponing the Work 4. Tree-Structured Programs Look-Ahead in games I5. Pointers and Pitfalls
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 Stack DIDID space AAALALAALA DIDIDIDID 团团的门 data Time 数据结构是递归的 Start +- Finish
5.1 Stacks and Trees 数据结构是递归的
THEOREM 5.1 During the traversal of any tree, vertices are added to or deleted from 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
THEOREM 5.1 During the traversal of any tree, vertices are added to or deleted from 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 o The circles in a tree diagram are called vertices or nodes o The top of the tree is called its root o the vertices immediately below a given vertex are callled 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 分支 ◆Th兄第 ting a vertex with one immed ately above or below is called a branch. 9 Siblings are vertices with the same parent
Tree-Diagram Definitions The circles in a tree diagram are called vertices or nodes. The top of the tree is called 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 below is called a branch. Siblings are vertices with the same parent. 分支 兄弟
9 A vertex with no children is called a leaf or an externa/ 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 to its successor is called a path. o 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
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 to 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 Recursive Definition Informal definition: The factorial function of a positive integer IS n!=nx(n-1)x.XI 定义是递归的 Formal definition 雪n=0时 n*(n-1)!,当n≥1时
Factorials: A Recursive Definition Informal definition: The factorial function of a positive integer is n! = n(n-1)…1 Formal definition: − = = 当 时 当 时 n (n 1)!, n 1 1, n 0 n! 定义是递归的
boundary Every recursive processconsists of two parts: A smallest, base case that is processed without recursion and recursion a general method that reduces a particular case to one or more ot the smaller cases thereby making progress toward eventually reducing the problem all the way to the base case
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 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
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); / 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 tempused for temporary storage has been returned to its starting 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. /
void move(int count, int start, int finish, int temp); /* 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 starting 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( i move(disks, 1, 3, 2);3 void move(int count, int start int nish, int temp) i if (count>O i move count-1, start, temp, nish); cout < Move disk < count < from < start < to<< finish <<< endl move count-1, temp, nish, start; Please see pg. 166-167 figure 5. 4-5.5
main( ) { move(disks, 1, 3, 2); } void move(int count, int start, int nish, int temp) { if (count > 0) { move(count - 1, start, temp, nish); cout << "Move disk " << count << " from " << start << " to " << finish << "." << endl; move(count - 1, temp, nish, start); } } Please see pg. 166-167 figure 5.4 - 5.5
