2008级计算机专业数据结构 内部资料,仅供课堂教学使用 Chapter 5 ReCUrSIoN P 157 1. Introduction to recursion 3. Backtracking: Postponing the Work a) The Eight-Queens Puzzle (b)Recursion Trees (b)Review and refinement 2. Principles of Recursion 4. Tree-Structured Programs: Look- Ahead in Games 5.1 Introduction to Recursion 5.1.1 and 5.1.2 Stacks and trees P 158-160 THEOREM 5. 1 During the traversal of any tree, vertices are added to or deleted from the path back to the root the fashion of a stack. Given any stack, conversely, a tree can be drawn to portray the life history of the stack, items are pushed onto or popped from it Tree-Diagram Definitions P159 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. A vertex with no children is called a leaf or an external vertex second. A sequence of branches in which each is adjacent to its successor is called a path ex of the Two branches of a tree are adjacent if the lower vertex of the first branch is the upper ve 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 e The depth or level of a vertex is the number of branches on a path from the root to the vertex. 5.1.3 Factorials. A Recursive Definition p 160 Informal definition P. 160 Formal definition Every recursive process consists of two parts: P. 161 A smallest, base case that is processed without recursion 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 Recursive program P. 162 5.1.4 Towers of Hanoi P 163 Rules: Move only one disk at a time; No larger disk can be on top of a smaller disk Refinement: P164 Program for Hanoi: Main program, Recursive function P165 Program Tracing and Analysis P.166-167 5.2 Principles of Recursion 5.2. 1 Designing Recursive Algorithms iTems P 170 5.2.2 Implementation of Recursion P171-173 e Multiple Processors: Concurr Recursion can run on mmpe, ency: Processes that take place simultaneously are called concurrent Single Processor Implementation: Recursion can use multiple storage areas with a single processor Example of Re-entrant Processes: P. 173 Execution Tree and stack frames P174 5.2. 3 Tail Recursion DEFINITION: Tail recursion occurs when the last-executed statement of a function is a recursive call to itself. If the last-executed statement of a function is a recursive call to the function itself. then this call can be eliminated by reassigning the calling parameters to the values specified in the recursive call, and then repeating the whole function. P. 175 Hanoi without Tail recursion P 176
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 5 RECURSION P.157 ----------------------------------------------------------------------------------------------------------------------------------------------- 1. Introduction to Recursion (a) Stack Frames (b) Recursion Trees (c) Examples 2. Principles of Recursion 3. Backtracking: Postponing the Work (a) The Eight-Queens Puzzle (b) Review and Refinem ent (c) Analysis 4. Tree-Structured Programs: Look-Ahead in Games [5.1]Introduction to Recursion 5.1.1 and 5.1.2 Stacks and Trees P. 158-160 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 P. 159 ⚫ 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. ⚫ 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. 5.1.3 Factorials: A Recursive Definition P. 160 Informal definition P. 160 Formal definition P. 161 Every recursive process consists of two parts: P. 161 ⚫ A smallest, base case that is processed without recursion; ⚫ 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. Recursive program P. 162 5.1.4 Towers of Hanoi P. 163 Rules: Move only one disk at a time; No larger disk can be on top of a smaller disk. Refinement: P. 164 Program for Hanoi: Main program, Recursive function P. 165 Program Tracing and Analysis P. 166-167 [5.2] Principles of Recursion 5.2.1 Designing Recursive Algorithms 5 Items P. 170 5.2.2 Implementation of Recursion P. 171-173 ⚫ Multiple Processors: Concurrency: Processes that take place simultaneously are called concurrent. Recursion can run on multiple processors concurrently. P. 171 ⚫ Single Processor Implementation: Recursion can use multiple storage areas with a single processor. ⚫ Example of Re-entrant Processes: P. 173 Execution Tree and Stack Frames P. 174 5.2.3 Tail Recursion DEFINITION: Tail recursion occurs when the last-executed statement of a function is a recursive call to itself. If the last-executed statement of a function is a recursive call to the function itself, then this call can be eliminated by reassigning the calling parameters to the values specified in the recursive call, and then repeating the whole function. P. 175 Hanoi Without Tail Recursion P. 176
2008级计算机专业数据结构课堂教学笔记 内部资料,仅供课堂教学使用 5.2.4 Calculating Factorials Recursive; Nonrecursive; Example: P 177 Fibonacci Numbers Definition: Recursive function: Nonrecursive function P. 178-179 5.3 Backtracking: Postponing the Work Eight Queens Puzzle P183 Four Queens Solution P 184 Program Outline Recursive function: P 184 Main program Methods in the queens Class P 187 The Backtracking Function P The first Data Structure P 188 Sample Results P 191 void Queens insert(int col) P. 189 Queens Queens(int size) P.189 bool Queens : unguarded( int col) const P. 191 Components of a Chessboard P 190 Revised data structures p193 Sample results P.194 Class Declaration P. 193 Constructor P.193 Insertion P.193 Recursion tree P 195 5.4 Tree-Structured Programs: Look-Ahead in Games P.198 5. 4.1 Game Trees P 198 5.4.3 Algorithm Development P201 Use two classes called Move and Board. A Move object represents a single game move. A Board object represents a single game position The class Move requires only constructor methods The class board requires methods to initialize the board, to detect whether the game is over, to play a move that is passed as a parameter, to evaluate a position, and to supply a list of all current legal moves The method legal moves uses a stack to return the current move options The method better uses two integer parameters and returns a nonzero result if the(current) mover would prefer a game value given by the first rather than the second parameter The method worst case returns a constant value that the mover would like less than the value of any possible game position class board: P202 5.4.4 Look-Ahead algorithm P203 5.4.5 Tic-Tac-Toe P204 o The tic-tac-toe grid is a 3x3 array of integers, with0 to denote an empty square and the values I and 2 to denote squares occupied by the first and second players, respectively A Move object stores the coordinates of a square on the gri The board class contains private data members to record the current game state in a 3 x 3 array and to record how many moves have been played The game is finished either after nine moves have been played or when one or the other player has actually won The legal moves available for a player are just the squares with a value of o e Evaluate a Board position as O if neither player has yet won; however, if one or other player has won, we shall evaluate the position according to the rule that quick wins are considered very good, and quick losses are considered very bad a program that sets the depth of look-ahead to a value of 9 or more will play a perfect game, since it will al ways be able to look ahead to a situation where its evaluation of the position is exact. A program with shallower depth can make mistakes, because it might finish its look-ahead with a collection of positions
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 5.2.4Calculating Factorials Recursive; Nonrecursive; Example: P. 177 Fibonacci Numbers Definition; Recursive function; Nonrecursive function: P. 178-179 [5.3] Backtracking: Postponing the Work Eight Queens Puzzle P. 183 Four Queens Solution P. 184 Program Outline Recursive function: P. 184 Main program: P. 186 Methods in the Queens Class P. 187 The Backtracking Function P. 188 The First Data Structure P. 188 Sample Results P. 191 void Queens :: insert(int col) P. 189 Queens :: Queens(int size) P. 189 bool Queens :: unguarded(int col) const P. 191 Components of a Chessboard P. 190 Revised Data Structures P. 193 Sample Results P. 194 Class Declaration P. 193 Constructor P. 193 Insertion P. 193 Recursion Tree P . 195 [5.4] Tree-Structured Programs: Look-Ahead in Games P. 198 5.4.1 Game Trees P. 198 5.4.3 Algorithm Development P. 201 Use two classes called Move and Board. A Move object represents a single game move. A Board object represents a single game position. The class Move requires only constructor methods. The class Board requires methods to initialize the Board, to detect whether the game is over, to play a move that is passed as a parameter, to evaluate a position, and to supply a list of all current legal moves. The method legal_moves uses a stack to return the current move options. The method better uses two integer parameters and returns a nonzero result if the (current) mover would prefer a game value given by the first rather than the second parameter. The method worst_case returns a constant value that the mover would like less than the value of any possible game position. class Board: P. 202 5.4.4 Look-Ahead Algorithm P. 203 5.4.5 Tic-Tac-Toe P. 204 ⚫ The tic-tac-toe grid is a 3×3 array of integers, with 0 to denote an empty square and the values 1 and 2 to denote squares occupied by the first and second players, respectively. ⚫ A Move object stores the coordinates of a square on the grid. ⚫ The Board class contains private data members to record the current game state in a 3 × 3 array and to record how many moves have been played. ⚫ The game is finished either after nine moves have been played or when one or the other player has actually won. ⚫ The legal moves available for a player are just the squares with a value of 0. ⚫ Evaluate a Board position as 0 if neither player has yet won; however, if one or other player has won, we shall evaluate the position according to the rule that quick wins are considered very good, and quick losses are considered very bad. ⚫ A program that sets the depth of look-ahead to a value of 9 or more will play a perfect game, since it will always be able to look ahead to a situation where its evaluation of the position is exact. A program with shallower depth can make mistakes, because it might finish its look-ahead with a collection of positions
2008级计算机专业数据结构课堂教学笔记 内部资料,仅供课堂教学使用 that misleadingly evaluate as zero The move class P The board class p 20 Constructor void Board: play (Move try it) P. 206 int Board: the winner()const bool Board: done()const P.206 int Board: legal moves( Stack &moves)const 207 int Board: evaluate()const P.207 Pointers and pitfalls 15 items P 209 Errata p. 195, Fig. 5. 15, bottom: Two arrow shafts are missing
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 that misleadingly evaluate as zero. The Move Class P. 204 The Board Class P. 205 Constructor P. 205 void Board :: play(Move try it) P. 206 int Board :: the_winner( ) const P. 206 bool Board :: done( ) const P. 206 int Board :: legal_moves(Stack &moves) const P. 207 int Board :: evaluate( ) const P. 207 Pointers and Pitfalls 15 items P.209 ------------------------------------------------------------------------------------------------------------------------------- Errata p. 195, Fig. 5.15, bottom: Two arrow shafts are missing. -------------------------------------------------------------------------------------------------------------------------------