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 1762008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 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