Thinking Recursively

Description

The process of solving large problems by breaking them down into smaller, more simple problems that have identical forms. Thinking Recursively: A small text to solve large problems. Concentrating on the practical value of recursion. this text, the first of its kind, is essential to computer science students’ education. In this text, students will learn the concept and programming applications of recursive thinking. This will ultimately prepare students for advanced topics in computer science such as compiler construction, formal language theory, and the mathematical foundations of computer science. Key Features: Concentration on the practical value of recursion. Eleven chapters emphasizing recursion as a unified concept. Extensive discussion of the mathematical concepts which help the students to develop an appropriate conceptual model. Large number of imaginative examples with solutions. Large sets of exercises. Cover......Page 1 Copyright......Page 5 Preface......Page 8 Contents......Page 10 1-1 An Illustration of the Recursive Approach......Page 12 1-2 Mondrian and Computer Art......Page 15 1-3 Characteristics of Recursive Algorithms......Page 18 1-4 Nonterminating Recursion......Page 19 1-5 Thinking about Recursion—Two Perspectives......Page 20 Exercises......Page 22 2 Mathematical Preliminaries......Page 24 2-1 Mathematical lnduction......Page 25 2-2 Computational Complexity......Page 30 Exercises......Page 38 3 Recursive Functions......Page 42 3-2 Factorials......Page 43 3-3 The Fibonacci Sequence......Page 47 Exercises......Page 53 4 The Procedural Approach......Page 58 4-1 Numeric Output......Page 60 4-2 Generating a Primer (with apologies to Dick and Jane)......Page 65 Exercises......Page 72 5 The Tower of Hanoi......Page 74 5-1 The Recursive Solution......Page 75 5-2 The Reductionistic View......Page 78 Exercises......Page 84 6 Permutations......Page 86 Exercises......Page 90 7 Sorting......Page 94 7-1 Selection Sorting......Page 96 7-2 Merge Sorting......Page 100 Exercises......Page 111 8 Intelligent Algorithms......Page 114 8-1 Backtracking through a Maze......Page 115 8-2 Lookahead Strategies......Page 124 Exercises......Page 131 9 Graphical Applications......Page 136 9-1 Computer Graphics in Pascal......Page 137 9-2 Fractal Geometry......Page 139 Exercises......Page 145 10 Recursive Data......Page 150 10-1 Representing Strings as Linked Lists......Page 152 10-2 Binary Trees......Page 156 10-3 Expression Trees......Page 163 Exercises......Page 167 11-1 The Control Stack Model......Page 172 11-2 Simulating Recursion......Page 177 Bibliography......Page 186 Index......Page 188