Introduction to Recursive Programming

Description

2.1 Template For Designing Recursive Algorithms......Page 3 Preface......Page 10 Figures......Page 16 Tables......Page 26 Listings......Page 27 1.1 Recognizing Recursion......Page 34 1.2 Problem Decomposition......Page 39 1.3 Recursive Code......Page 46 1.4.1 Mathematical Proofs By Induction......Page 52 1.4.2 Recursive Leap Of Faith......Page 54 1.5 Recursion Vs. Iteration......Page 57 1.6.2 Tail Recursion......Page 59 1.6.4 Mutual Recursion......Page 60 1.7 Exercises......Page 61 2 Methodology for Recursive Thinking......Page 63 2.2 Size Of The Problem......Page 64 2.3 Base Cases......Page 66 2.4 Problem Decomposition......Page 69 2.5.1 Thinking Recursively Through Diagrams......Page 73 2.5.2 Concrete Instances......Page 77 2.5.4 Procedures......Page 79 2.5.5 Several Subproblems......Page 81 2.6 Testing......Page 84 2.7 Exercises......Page 87 3.1 Mathematical Preliminaries......Page 89 3.1.2 Binomial Coefficients......Page 90 3.1.3 Limits And L’hopital’s Rule......Page 91 3.1.4 Sums And Products......Page 92 3.1.6 Trigonometry......Page 98 3.1.7 Vectors And Matrices......Page 99 3.2 Computational Time Complexity......Page 102 3.2.1 Order Of Growth Of Functions......Page 103 3.2.2 Asymptotic Notation......Page 105 3.3 Recurrence Relations......Page 108 3.3.1 Expansion Method......Page 112 3.3.2 General Method For Solving Difference Equations......Page 121 3.4 Exercises......Page 133 4 Linear Recursion - Basic Algorithms......Page 137 4.1.1 Power Function......Page 138 4.1.2 Slow Addition......Page 142 4.1.3 Double Sum......Page 145 4.2.1 Binary Representation Of A Nonnegative Integer......Page 147 4.2.2 Decimal To Base B Conversion......Page 149 4.3.1 Reversing A String......Page 151 4.3.2 Is A String A Palindrome......Page 152 4.4.1 Selection Sort......Page 153 4.4.2 Horner’s Method For Evaluating Polynomials......Page 156 4.4.3 A Row Of Pascal’s Triangle......Page 157 4.4.4 Ladder Of Resistors......Page 159 4.5 Exercises......Page 161 5 Linear Recursion - Tail Recursion......Page 165 5.1.1 Does A Nonnegative Integer Contain A Particular Digit......Page 166 5.1.2 Equal Strings......Page 168 5.2.1 Linear Search......Page 171 5.2.2 Binary Search In A Sorted List......Page 174 5.3 Binary Search Trees......Page 175 5.3.1 Searching For An Item......Page 176 5.3.2 Inserting An Item......Page 179 5.4 Partitioning Schemes......Page 180 5.4.1 Basic Partitioning Scheme......Page 181 5.4.2 Hoare’s Partitioning Method......Page 182 5.5 The Quickselect Algorithm......Page 187 5.6 Bisection Algorithm For Root Finding......Page 189 5.7 The Woodcutter Problem......Page 190 5.8 Euclid’s Algorithm......Page 196 5.9 Exercises......Page 199 6 Multiple Recursion - Divide & Conquer......Page 203 6.1 Is A List Sorted In Ascending Order......Page 204 6.2 Sorting......Page 205 6.2.1 The Merge Sort Algorithm......Page 206 6.2.2 The Quicksort Algorithm......Page 209 6.3 Majority Element In A List......Page 212 6.4 Fast Integer Multiplication......Page 215 6.5 Matrix Multiplication......Page 218 6.5.1 Divide And Conquer Matrix Multiplication......Page 219 6.5.2 Strassen’s Matrix Multiplication Algorithm......Page 222 6.6 The Tromino Tiling Problem......Page 223 6.7 The Skyline Problem......Page 228 6.8 Exercises......Page 235 7.1 Swamp Traversal......Page 237 7.2 Towers Of Hanoi......Page 241 7.3 Tree Traversals......Page 245 7.3.1 Inorder Traversal......Page 247 7.3.2 Preorder And Postorder Traversals......Page 248 7.4 Longest Palindrome Substring......Page 249 7.5.1 Koch Snowflake......Page 252 7.5.2 Sierpinski’s Carpet......Page 256 7.6 Exercises......Page 258 8 Counting Problems......Page 266 8.1 Permutations......Page 267 8.2 Variations With Repetition......Page 269 8.3 Combinations......Page 271 8.4 Staircase Climbing......Page 273 8.5 Manhattan Paths......Page 275 8.6 Convex Polygon Triangulations......Page 276 8.7 Circle Pyramids......Page 279 8.8 Exercises......Page 281 9 Mutual Recursion......Page 284 9.1 Parity Of A Number......Page 285 9.2 Multiplayer Games......Page 286 9.3 Rabbit Population Growth......Page 287 9.3.1 Adult And Baby Rabbit Pairs......Page 288 9.3.2 Rabbit Family Tree......Page 289 9.4.1 Water Flow Between Cities......Page 294 9.4.2 Water Discharge At Each City......Page 296 9.5 Cyclic Towers Of Hanoi......Page 299 9.6 Grammars And Recursive Descent Parsers......Page 304 9.6.1 Tokenization Of The Input String......Page 305 9.6.2 Recursive Descent Parser......Page 310 9.7 Exercises......Page 319 10 Program Execution......Page 322 10.1 Control Flow Between Subroutines......Page 323 10.2 Recursion Trees......Page 328 10.2.1 Runtime Analysis......Page 334 10.3 The Program Stack......Page 336 10.3.1 Stack Frames......Page 337 10.3.2 Stack Traces......Page 340 10.3.3 Computational Space Complexity......Page 341 10.3.4 Maximum Recursion Depth And Stack Overflow Errors......Page 343 10.3.5 Recursion As An Alternative To A Stack Data Structure......Page 344 10.4.1 Memoization......Page 348 10.4.2 Dependency Graph And Dynamic Programming......Page 353 10.5 Exercises......Page 356 11.1 Tail Recursion Vs. Iteration......Page 364 11.2.1 Factorial......Page 368 11.2.2 Decimal To Base B Conversion......Page 371 11.3.2 The Mccarthy 91 Function......Page 373 11.3.3 The Digital Root......Page 374 11.4 Tail And Nested Recursion Through Function Generalization......Page 375 11.4.1 Factorial......Page 376 11.4.2 Decimal To Base B Conversion......Page 379 11.5 Exercises......Page 381 12 Multiple Recursion - Backtracking......Page 383 12.1.1 Partial And Complete Solutions......Page 384 12.1.2 Recursive Structure......Page 386 12.2 Generating Combinatorial Entities......Page 388 12.2.1 Subsets......Page 389 12.2.2 Permutations......Page 394 12.3 The N-queens Problem......Page 398 12.3.1 Finding Every Solution......Page 400 12.4 Subset Sum Problem......Page 402 12.5 Path Through A Maze......Page 407 12.6 The Sudoku Puzzle......Page 414 12.7 0-1 Knapsack Problem......Page 418 12.7.1 Standard Backtracking Algorithm......Page 419 12.7.2 Branch And Bound Algorithm......Page 423 12.8 Exercises......Page 427 Reading......Page 433 Index......Page 437