Introduction to recursive programming

Cover......Page 1
Half Title......Page 2
Title......Page 4
Copyright......Page 5
Dedication......Page 6
 2.1 Template For Designing Recursive Algorithms......Page 8
Preface......Page 16
List Of Figures......Page 22
List Of Tables......Page 32
List Of Listings......Page 34
 1.1 Recognizing Recursion......Page 42
 1.2 Problem Decomposition......Page 48
 1.3 Recursive Code......Page 55
  1.4.1 Mathematical Proofs By Induction......Page 61
  1.4.2 Recursive Leap Of Faith......Page 63
 1.5 Recursion Vs. Iteration......Page 66
  1.6.2 Tail Recursion......Page 68
  1.6.4 Mutual Recursion......Page 69
 1.7 Exercises......Page 70
Chapter 2   Methodology For Recursive Thinking......Page 72
 2.2 Size Of The Problem......Page 73
 2.3 Base Cases......Page 75
 2.4 Problem Decomposition......Page 78
  2.5.1 Thinking Recursively Through Diagrams......Page 82
  2.5.2 Concrete Instances......Page 86
  2.5.4 Procedures......Page 88
  2.5.5 Several Subproblems......Page 90
 2.6 Testing......Page 93
 2.7 Exercises......Page 96
 3.1 Mathematical Preliminaries......Page 98
  3.1.2 Binomial Coefficients......Page 99
  3.1.3 Limits And L’hopital’s Rule......Page 100
  3.1.4 Sums And Products......Page 101
  3.1.6 Trigonometry......Page 107
  3.1.7 Vectors And Matrices......Page 108
 3.2 Computational Time Complexity......Page 111
  3.2.1 Order Of Growth Of Functions......Page 112
  3.2.2 Asymptotic Notation......Page 114
 3.3 Recurrence Relations......Page 117
  3.3.1 Expansion Method......Page 121
  3.3.2 General Method For Solving Difference Equations......Page 130
 3.4 Exercises......Page 142
Chapter 4   Linear Recursion I: Basic Algorithms......Page 146
  4.1.1 Power Function......Page 147
  4.1.2 Slow Addition......Page 151
  4.1.3 Double Sum......Page 154
  4.2.1 Binary Representation Of A Nonnegative Integer......Page 156
  4.2.2 Decimal To Base B Conversion......Page 158
  4.3.1 Reversing A String......Page 160
  4.3.2 Is A String A Palindrome......Page 161
  4.4.1 Selection Sort......Page 162
  4.4.2 Horner’s Method For Evaluating Polynomials......Page 165
  4.4.3 A Row Of Pascal’s Triangle......Page 166
  4.4.4 Ladder Of Resistors......Page 168
 4.5 Exercises......Page 170
Chapter 5   Linear Recursion Ii: Tail Recursion......Page 174
  5.1.1 Does A Nonnegative Integer Contain A Particular  Digit......Page 175
  5.1.2 Equal Strings......Page 177
  5.2.1 Linear Search......Page 180
  5.2.2 Binary Search In A Sorted List......Page 183
 5.3 Binary Search Trees......Page 184
  5.3.1 Searching For An Item......Page 185
  5.3.2 Inserting An Item......Page 188
 5.4 Partitioning Schemes......Page 189
  5.4.1 Basic Partitioning Scheme......Page 190
  5.4.2 Hoare’s Partitioning Method......Page 191
 5.5 The Quickselect Algorithm......Page 196
 5.6 Bisection Algorithm For Root Finding......Page 198
 5.7 The Woodcutter Problem......Page 199
 5.8 Euclid’s Algorithm......Page 205
 5.9 Exercises......Page 208
Chapter 6   Multiple Recursion I: Divide And Conquer......Page 212
 6.1 Is A List Sorted In Ascending Order......Page 213
 6.2 Sorting......Page 214
  6.2.1 The Merge Sort Algorithm......Page 215
  6.2.2 The Quicksort Algorithm......Page 218
 6.3 Majority Element In A List......Page 221
 6.4 Fast Integer Multiplication......Page 224
 6.5 Matrix Multiplication......Page 227
  6.5.1 Divide And Conquer Matrix Multiplication......Page 228
  6.5.2 Strassen’s Matrix Multiplication Algorithm......Page 231
 6.6 The Tromino Tiling Problem......Page 232
 6.7 The Skyline Problem......Page 237
 6.8 Exercises......Page 244
 7.1 Swamp Traversal......Page 246
 7.2 Towers Of Hanoi......Page 250
 7.3 Tree Traversals......Page 254
  7.3.1 Inorder Traversal......Page 256
  7.3.2 Preorder And Postorder Traversals......Page 257
 7.4 Longest Palindrome Substring......Page 258
  7.5.1 Koch Snowflake......Page 261
  7.5.2 Sierpinski’s Carpet......Page 265
 7.6 Exercises......Page 267
Chapter 8   Counting Problems......Page 276
 8.1 Permutations......Page 277
 8.2 Variations With Repetition......Page 279
 8.3 Combinations......Page 281
 8.4 Staircase Climbing......Page 283
 8.5 Manhattan Paths......Page 285
 8.6 Convex Polygon Triangulations......Page 286
 8.7 Circle Pyramids......Page 289
 8.8 Exercises......Page 291
Chapter 9   Mutual Recursion......Page 294
 9.1 Parity Of A Number......Page 295
 9.2 Multiplayer Games......Page 296
 9.3 Rabbit Population Growth......Page 297
  9.3.1 Adult And Baby Rabbit Pairs......Page 298
  9.3.2 Rabbit Family Tree......Page 299
  9.4.1 Water Flow Between Cities......Page 304
  9.4.2 Water Discharge At Each City......Page 306
 9.5 Cyclic Towers Of Hanoi......Page 309
 9.6 Grammars And Recursive Descent Parsers......Page 314
  9.6.1 Tokenization Of The Input String......Page 315
  9.6.2 Recursive Descent Parser......Page 320
 9.7 Exercises......Page 329
Chapter 10   Program Execution......Page 332
 10.1 Control Flow Between Subroutines......Page 333
 10.2 Recursion Trees......Page 338
  10.2.1 Runtime Analysis......Page 344
 10.3 The Program Stack......Page 346
  10.3.1 Stack Frames......Page 347
  10.3.2 Stack Traces......Page 350
  10.3.3 Computational Space Complexity......Page 351
  10.3.4 Maximum Recursion Depth And Stack Overflow  Errors......Page 353
  10.3.5 Recursion As An Alternative To A Stack Data  Structure......Page 354
  10.4.1 Memoization......Page 358
  10.4.2 Dependency Graph And Dynamic Programming......Page 363
 10.5 Exercises......Page 366
 11.1 Tail Recursion Vs. Iteration......Page 374
  11.2.1 Factorial......Page 378
  11.2.2 Decimal To Base B Conversion......Page 381
  11.3.2 The Mccarthy 91 Function......Page 383
  11.3.3 The Digital Root......Page 384
 11.4 Tail And Nested Recursion Through Function  Generalization......Page 385
  11.4.1 Factorial......Page 386
  11.4.2 Decimal To Base B Conversion......Page 389
 11.5 Exercises......Page 391
Chapter 12   Multiple Recursion Iii: Backtracking......Page 394
  12.1.1 Partial And Complete Solutions......Page 395
  12.1.2 Recursive Structure......Page 397
 12.2 Generating Combinatorial Entities......Page 399
  12.2.1 Subsets......Page 400
  12.2.2 Permutations......Page 405
 12.3 The N-queens Problem......Page 409
  12.3.1 Finding Every Solution......Page 411
 12.4 Subset Sum Problem......Page 413
 12.5 Path Through A Maze......Page 418
 12.6 The Sudoku Puzzle......Page 425
 12.7 0-1 Knapsack Problem......Page 429
  12.7.1 Standard Backtracking Algorithm......Page 430
  12.7.2 Branch And Bound Algorithm......Page 434
 12.8 Exercises......Page 438
Further Reading......Page 444
Index......Page 448