| Description |
1 online resource (1 volume) : illustrations |
|
data file |
| Bibliography |
Includes bibliographical references and index. |
| Summary |
Recursion is one of the most fundamental concepts in computer science and a key programming technique that allows computations to be carried out repeatedly. Despite the importance of recursion for algorithm design, most programming books do not cover the topic in detail, despite the fact that numerous computer programming professors and researchers in the field of computer science education agree that recursion is difficult for novice students. Introduction to Recursive Programming provides a detailed and comprehensive introduction to recursion. This text will serve as a useful guide for anyone who wants to learn how to think and program recursively, by analyzing a wide variety of computational problems of diverse difficulty. It contains specific chapters on the most common types of recursion (linear, tail, and multiple), as well as on algorithm design paradigms in which recursion is prevalent (divide and conquer, and backtracking). Therefore, it can be used in introductory programming courses, and in more advanced classes on algorithm design. The book also covers lower-level topics related to iteration and program execution, and includes a rich chapter on the theoretical analysis of the computational cost of recursive programs, offering readers the possibility to learn some basic mathematics along the way. It also incorporates several elements aimed at helping students master the material. First, it contains a larger collection of simple problems in order to provide a solid foundation of the core concepts, before diving into more complex material. In addition, one of the book's main assets is the use of a step-by-step methodology, together with specially designed diagrams, for guiding and illustrating the process of developing recursive algorithms. Furthermore, the book covers combinatorial problems and mutual recursion. These topics can broaden students' understanding of recursion by forcing them to apply the learned concepts differently, or in a more sophisticated manner. The code examples have been written in Python 3, but should be straightforward to understand for students with experience in other programming languages. Finally, worked out solutions to over 120 end-of-chapter exercises are available for instructors. |
| Contents |
Chapter 1 Basic concepts of recursive programming -- 1.1 Recognizing recursion -- 1.2 Problem decomposition -- 1.3 Recursive code -- 1.4 Induction -- 1.4.1 Mathematical proofs by induction -- 1.4.2 Recursive leap of faith -- 1.4.3 Imperative vs. declarative programming -- 1.5 Recursion vs. iteration -- 1.6 Types of recursion -- 1.6.1 Linear recursion -- 1.6.2 Tail recursion -- 1.6.3 Multiple recursion -- 1.6.4 Mutual recursion -- 1.6.5 Nested recursion -- 1.7 Exercises -- Chapter 2 Methodology for recursive thinking -- 2.1 Template for designing recursive algorithms -- 2.2 Size of the problem -- 2.3 Base cases -- 2.4 Problem decomposition -- 2.5 Recursive cases, induction, and diagrams -- 2.5.1 Thinking recursively through diagrams -- 2.5.2 Concrete instances -- 2.5.3 Alternative notations -- 2.5.4 Procedures -- 2.5.5 Several subproblems -- 2.6 Testing -- 2.7 Exercises -- Chapter 3 Runtime analysis of recursive algorithms -- 3.1 Mathematical preliminaries -- 3.1.1 Power and logarithms -- 3.1.2 Bionomial coefficients -- 3.1.3 Limits and L'Hopital's rules -- 3.1.4 Sums and products -- 3.1.5 Floors and ceilings -- 3.1.6 Trigonometry -- 3.1.7 Vectors and matrices -- 3.2 Computational time complexity -- 3.2.1 Order of growth of functions -- 3.2.2 Asymptotic notation -- 3.3 Recurrence relations -- 3.3.1 Expansion method -- 3.3.2 General method for solving difference equations -- 3.4 Exercises -- Chapter 4 Linear recursion I : basic algorithms -- 4.1 Arithmetic operations -- 4.1.1 Power function -- 4.1.2 Slow addition -- 4.1.3 Double sum -- 4.2 Basic conversion -- 4.2.1 Binary representation of a nonnegative integer -- 4.2.2 Decimal to base b conversion -- 4.3 Strings -- 4.3.1 Reversing a string -- 4.3.2 Is a string a palindrome? -- 4.4 Additional problems -- 4.4.1 Selection sort -- 4.4.2 Horner's method for evaluating polynomials -- 4.4.3 A row of Pascal's triangle -- 4.4.4 Ladder of resistors -- 4.5 Exercises -- Chapter 5 Linear recursion II : tail recursion -- 5.1 Boolean functions -- 5.1.1 Does a nonnegative integer contain a particular digit? -- 5.1.2 Equal strings? -- 5.2 Searching algorithms for lists -- 5.2.1 Linear search -- 5.2.2 Binary search in a sorted list -- 5.3 Binary search trees -- 5.3.1 Searching for an item -- 5.3.2 Inserting an item -- 5.4 Partitioning schemes -- 5.4.1 Basic partitioning scheme -- 5.4.2 Hoare's partitioning method -- 5.5 The quickselect algorithm -- 5.6 Bisection algorithm for root finding -- 5.7 The woodcutter problem -- 5.8 Euclid's algorithm -- 5.9 Exercises |
|
Chapter 6 Multiple recursion I : divide and conquer -- 6.1 Is a list sorted in ascending order? -- 6.2 Sorting -- 6.2.1 The merge sort algorithm -- 6.2.2 The quicksort algorithm -- 6.3 Majority element in a list -- 6.4 Fast integer multiplication -- 6.5 Matrix multiplication -- 6.5.1 Divide and conquer matrix multiplication -- 6.5.2 Strassen's matrix multiplication algorithm -- 6.6 The tromino tiling problem -- 6.7 The skyline problem -- 6.8 Exercises -- Chapter 7 Multiple recursion II : puzzles, fractals, and more ... 7.1 Swamp traversal -- 7.2 Towers of Hanoi -- 7.3 Tree traversals -- 7.3.1 Inorder traveresal -- 7.3.2 Preorder and postorder traversals -- 7.4 Longest palindrome substring -- 7.5 Fractals -- 7.5.1 Koch snowflake -- 7.5.2 Sierpiński's carpet -- 7.6 Exercises -- Chapter 8 Counting problems -- 8.1 Permutations -- 8.2 Variations with repetition -- 8.3 Combinations -- 8.4 Staircase climbing -- 8.5 Manhattan paths -- 8.6 Convex polygon triangulations -- 8.7 Circle pyramids -- 8.8 Exercises -- Chapter 9 Mutual recursion -- 9.1 Parity of a number -- 9.2 Multiplayer games -- 9.3 Rabbit population growth -- 9.3.1 Adult and baby rabbit pairs -- 9.3.2 Rabbit family tree -- 9.4 Water treatment plants puzzle -- 9.4.1 Water flow between cities -- 9.4.2 Water discharge at each city -- 9.5 Cyclic towers of Hanoi -- 9.6 Grammars and recursive descent parsers -- 9.6.1 Tokenization of the input string -- 9.6.2 Recursive descent parser -- 9.7 Exercises -- Chapter 10 Program execution -- 10.1 Control flow between subroutines -- 10.2 Recursion trees -- 10.2.1 Runtime analysis -- 10.3 The program stack -- 10.3.1 Stack frames -- 10.3.2 Stack traces -- 10.3.3 Computational space complexity -- 10.3.4 Maximum recursion depth and stack overflow errors -- 10.3.5 Recursion as an alternative to a stack data structure -- 10.4 Memoization and dynamic programming -- 10.4.1 Memoization -- 10.4.2 Dependency graph and dynamic programming -- 10.5 Exercises -- Chapter 11 Tail recursion revisited and nested recursion -- 11.1 Tail recursion vs. iteration -- 11.2 Tail recursion by thinking iteratively -- 11.2.1 Factorial -- 11.2.2 Decimal to base b conversion -- 11.3 Nested recursion -- 11.3.1 The Ackermann function -- 11.3.2 The McCarthy 91 function -- 11.3.3 The digital root -- 11.4 Tail and nested recursion through function generalization -- 11.4.1 Factorial -- 11.4.2 Decimal to base b conversion -- 11.5 Exercises -- Chapter 12 Multiple recursion III : backtracking -- 12.1 Introduction -- 12.1.1 Partial and complete solutions -- 12.1.2 Recursive structure -- 12.2 Generating combinatorial entities -- 12.2.1 Subsets -- 12.2.2 Permutations -- 12.3 The N-Queens problem -- 12.3.1 Finding every solution -- 12.3.2 Finding one solution -- 12.4 Subset sum problem -- 12.5 Path through a maze -- 12.6 The sudoku puzzle -- 12.7 0-1 knapsack problem -- 12.7.1 Standard backtracking algorithm -- 12.7.2 Branch and bound algorithm -- 12.8 Exercises. |
| Subject |
Recursive programming -- Textbooks.
|
|
Computer programming -- Textbooks.
|
|
Computer algorithms -- Textbooks.
|
|
Computer algorithms |
|
Computer programming |
|
Recursive programming |
| Genre |
Textbooks
|
| Other Form: |
Print version: Rubio Sánchez, Manuel. Introduction to recursive programming. Boca Raton, FL : CRC Press, Taylor & Francis Group, [2018] 9781138105218 (DLC) 2017016319 (OCoLC)978858123 |
| ISBN |
9781315120850 |
|
1315120852 |
|
9781498735308 |
|
1498735304 |
|
9781351647175 |
|
1351647172 |
|
113810521X |
|
9781138105218 |
|
1498735282 |
|
9781498735285 |
|
More Resources