The Recursive Book of Recursion: Ace the Coding Interview with Python and JavaScript

Brief Contents....9 Contents in Detail....11 Foreword....17 Acknowledgments....19 Introduction....21 Who Is This Book For?....23 About This Book....23 Hands-On, Experimental Computer Science....24 Installing Python....25 Running IDLE and the Python Code Examples....25 Running the JavaScript Code Examples in the Browser....26 Part I: Understanding Recursion....27 Chapter 1: What Is Recursion?....29 The Definition of Recursion....30 What Are Functions?....31 What Are Stacks?....33 What Is the Call Stack?....35 What Are Recursive Functions and Stack Overflows?....38 Base Cases and Recursive Cases....40 Code Before and After the Recursive Call....41 Summary....44 Further Reading....44 Practice Questions....45 Chapter 2: Recursion vs. Iteration....47 Calculating Factorials....48 The Iterative Factorial Algorithm....48 The Recursive Factorial Algorithm....49 Why the Recursive Factorial Algorithm Is Terrible....50 Calculating the Fibonacci Sequence....51 The Iterative Fibonacci Algorithm....52 The Recursive Fibonacci Algorithm....53 Why the Recursive Fibonacci Algorithm Is Terrible....55 Converting a Recursive Algorithm into an Iterative Algorithm....55 Converting an Iterative Algorithm into a Recursive Algorithm....57 Case Study: Calculating Exponents....60 Creating a Recursive Exponents Function....61 Creating an Iterative Exponents Function Based on Recursive Insights....63 When Do You Need to Use Recursion?....65 Coming Up with Recursive Algorithms....67 Summary....68 Further Reading....68 Practice Questions....68 Practice Projects....69 Chapter 3: Classic Recursion Algorithms....71 Summing Numbers in an Array....72 Reversing a String....75 Detecting Palindromes....78 Solving the Tower of Hanoi....80 Using Flood Fill....86 Using the Ackermann Function....91 Summary....93 Further Reading....93 Practice Questions....94 Practice Projects....95 Chapter 4: Backtracking and Tree Traversal Algorithms....97 Using Tree Traversal....98 A Tree Data Structure in Python and JavaScript....99 Traversing the Tree....100 Preorder Tree Traversal....101 Postorder Tree Traversal....102 Inorder Tree Traversal....103 Finding Eight-Letter Names in a Tree....104 Getting the Maximum Tree Depth....107 Solving Mazes....109 Summary....117 Further Reading....117 Practice Questions....118 Practice Projects....118 Chapter 5: Divide-and-Conquer Algorithms....119 Binary Search: Finding a Book in an Alphabetized Bookshelf....120 Quicksort: Splitting an Unsorted Pile of Books into Sorted Piles....123 Merge Sort: Merging Small Piles of Playing Cards into Larger Sorted Piles....130 Summing an Array of Integers....137 Karatsuba Multiplication....139 The Algebra Behind the Karatsuba Algorithm....145 Summary....145 Further Reading....146 Practice Questions....147 Practice Projects....148 Chapter 6: Permutations and Combinations....149 The Terminology of Set Theory....150 Finding All Permutations Without Repetition: A Wedding Seating Chart....152 Getting Permutations with Nested Loops: A Less-Than-Ideal Approach....156 Permutations with Repetition: A Password Cracker....157 Getting K-Combinations with Recursion....160 Get All Combinations of Balanced Parentheses....165 Power Set: Finding All Subsets of a Set....169 Summary....173 Further Reading....174 Practice Questions....174 Practice Projects....175 Chapter 7: Memoization and Dynamic Programming....177 Memoization....178 Top-Down Dynamic Programming....178 Memoization in Functional Programming....179 Memoizing the Recursive Fibonacci Algorithm....180 Python’s functools Module....184 What Happens When You Memoize Impure Functions?....185 Summary....186 Further Reading....187 Practice Questions....187 Chapter 8: Tail Call Optimization....189 How Tail Recursion and Tail Call Optimization Work....190 Accumulators in Tail Recursion....191 Limitations of Tail Recursion....192 Tail Recursion Case Studies....193 Tail Recursive Reverse String....194 Tail Recursive Find Substring....195 Tail Recursive Exponents....195 Tail Recursive Odd-Even....196 Summary....198 Further Reading....198 Practice Questions....199 Chapter 9: Drawing Fractals....201 Turtle Graphics....202 Basic Turtle Functions....203 The Sierpiński Triangle....205 The Sierpiński Carpet....209 Fractal Trees....213 How Long Is the Coast of Great Britain? The Koch Curve and Snowflake....216 The Hilbert Curve....220 Summary....223 Further Reading....223 Practice Questions....223 Practice Projects....224 Part II: Projects....227 Chapter 10: File Finder ....229 The Complete File-Search Program....230 The Match Functions....231 Finding the Files with an Even Number of Bytes....232 Finding the Filenames That Contain Every Vowel....232 The Recursive walk() Function....233 Calling the walk() Function....234 Useful Python Standard Library Functions for Working with Files....235 Finding Information About the File’s Name....235 Finding Information About the File’s Timestamps....236 Modifying Your Files....238 Summary....239 Further Reading....239 Chapter 11: Maze Generator ....241 The Complete Maze-Generator Program....242 Setting Up the Maze Generator’s Constants....247 Creating the Maze Data Structure....248 Printing the Maze Data Structure....249 Using the Recursive Backtracker Algorithm....251 Starting the Chain of Recursive Calls....254 Summary....255 Further Reading....255 Chapter 12: Sliding-Tile Solver....257 Solving 15-Puzzles Recursively....258 The Complete Sliding-Tile Solver Program....260 Setting Up the Program’s Constants....269 Representing the Sliding-Tile Puzzle as Data....269 Displaying the Board....270 Creating a New Board Data Structure....271 Finding the Coordinates of the Blank Space....271 Making a Move....272 Undoing a Move....273 Setting Up a New Puzzle....274 Recursively Solving the Sliding-Tile Puzzle....277 The solve() Function....277 The attemptMove() Function....279 Starting the Solver....281 Summary....282 Further Reading....283 Chapter 13: Fractal Art Maker....285 The Built-in Fractals....286 The Fractal Art Maker Algorithm....287 The Complete Fractal Art Maker Program....289 Setting Up Constants and the Turtle Configuration....293 Working with the Shape-Drawing Functions....293 The drawFilledSquare() Function....294 The drawTriangleOutline() Function....296 Using the Fractal Drawing Function....297 Setting Up the Function....298 Using the Specifications Dictionary....298 Applying the Specifications ....301 Creating the Example Fractals....303 Four Corners....303 Spiral Squares....303 Double Spiral Squares....304 Triangle Spiral....304 Conway’s Game of Life Glider....304 Sierpiński Triangle....305 Wave....305 Horn....305 Snowflake....306 Producing a Single Square or Triangle....306 Creating Your Own Fractals....307 Summary....308 Further Reading....308 Chapter 14: Droste Maker....309 Installing the Pillow Python Library....310 Painting Your Image....311 The Complete Droste Maker Program....312 Setting Up....314 Finding the Magenta Area....315 Resizing the Base Image....317 Recursively Placing the Image Within the Image....320 Summary....321 Further Reading....322 Index....323