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

Recursion has an intimidating reputation: it’s considered to be an advanced computer science topic frequently brought up in coding interviews. But there’s nothing magical about recursion.The Recursive Book of Recursion uses Python and JavaScript examples to teach the basics of recursion, exposing the ways that it’s often poorly taught and clarifying the fundamental principles of all recursive algorithms. You’ll learn when to use recursive functions (and, most importantly, when not to use them), how to implement the classic recursive algorithms often brought up in job interviews, and how recursive techniques can help solve countless problems involving tree traversal, combinatorics, and other tricky topics.

This project-based guide contains complete, runnable programs to help you learn: 

• How recursive functions make use of the call stack, a critical data structure almost never discussed in lessons on recursion
• How the head-tail and “leap of faith” techniques can simplify writing recursive functions
• How to use recursion to write custom search scripts for your filesystem, draw fractal art, create mazes, and more
• How optimization and memoization make recursive algorithms more efficient

Al Sweigart has built a career explaining programming concepts in a fun, approachable manner. If you’ve shied away from learning recursion but want to add this technique to your programming toolkit, or if you’re racing to prepare for your next job interview, this book is for you.