The Recursive Book of Recursion: Ace the Coding Interview with Python and JavaScript
An accessible yet rigorous crash course on recursive programming using Python and JavaScript examples.

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.
    1140041607
    The Recursive Book of Recursion: Ace the Coding Interview with Python and JavaScript
    An accessible yet rigorous crash course on recursive programming using Python and JavaScript examples.

    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.
    39.99 In Stock
    The Recursive Book of Recursion: Ace the Coding Interview with Python and JavaScript

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

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

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

    by Al Sweigart

    Paperback

    $39.99 
    • SHIP THIS ITEM
      In stock. Ships in 1-2 days.
    • PICK UP IN STORE

      Your local store may have stock of this item.

    Related collections and offers


    Overview

    An accessible yet rigorous crash course on recursive programming using Python and JavaScript examples.

    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.

    Product Details

    ISBN-13: 9781718502024
    Publisher: No Starch Press
    Publication date: 08/16/2022
    Pages: 328
    Product dimensions: 6.90(w) x 9.10(h) x 0.90(d)

    About the Author

    Al Sweigart is a software developer and tech book author living in Houston. Python is his favorite programming language, and he is the developer of several open source modules for it. His other books are freely available under a Creative Commons license on his website at https://www.inventwithpython.com/.

    Table of Contents

    Foreword xv

    Acknowledgments xvii

    Introduction xix

    Who Is This Book For? xxi

    About This Book xxi

    Hands-On, Experimental Computer Science xxii

    Installing Python xxiii

    Running IDLE and the Python Code Examples xxiii

    Running the JavaScript Code Examples in the Browser xxiv

    Part I Understanding Recursion 1

    1 What Is Recursion? 3

    The Definition of Recursion 4

    What Are Functions? 5

    What Are Stacks? 7

    What Is the Call Stack? 9

    What Are Recursive Functions and Stack Overflows? 12

    Base Cases and Recursive Cases 14

    Code Before and After the Recursive Call 15

    Summary 18

    Further Reading 18

    Practice Questions 19

    2 Recursion vs. Iteration 21

    Calculating Factorials 22

    The Iterative Factorial Algorithm 22

    The Recursive Factorial Algorithm 23

    Why the Recursive Factorial Algorithm Is Terrible 24

    Calculating the Fibonacci Sequence 25

    The Iterative Fibonacci Algorithm 26

    The Recursive Fibonacci Algorithm 27

    Why the Recursive Fibonacci Algorithm Is Terrible 29

    Converting a Recursive Algorithm into an Iterative Algorithm 29

    Converting an iterative Algorithm into a Recursive Algorithm 31

    Case Study: Calculating Exponents 34

    Creating a Recursive Exponents Function 35

    Creating an Iterative Exponents Function Based on Recursive insights 37

    When Do You Need to Use Recursion? 39

    Coming Up with Recursive Algorithms 41

    Summary 42

    Further Reading 42

    Practice Questions 42

    Practice Projects 43

    3 Classic Recursion Algorithms 45

    Summing Numbers in an Array 46

    Reversing a String 49

    Detecting Palindromes 52

    Solving the Tower of Hanoi 54

    Using Flood Fill 60

    Using the Ackermann Function 65

    Summary 67

    Further Reading 67

    Practice Questions 68

    Practice Projects 69

    4 Backtracking and Tree Traversal Algorithms 71

    Using Tree Traversal 72

    A Tree Data Structure in Python and JavaScript 73

    Traversing the Tree 74

    Preorder Tree Traversal 75

    Postorder Tree Traversal 76

    Inorder Tree Traversal 77

    Finding Eight-Letter Names in a Tree 78

    Getting the Maximum Tree Depth 81

    Solving Mazes 83

    Summary 91

    Further Reading 91

    Practice Questions 92

    Practice Projects 92

    5 Divide-and-Conquer Algorithms 93

    Binary Search: Finding a Book in an Alphabetized Bookshelf 94

    Quicksort: Splitting an Unsorted Pile of Books into Sorted Piles 97

    Merge Sort: Merging Small Piles of Playing Cards into Larger Sorted Piles 104

    Summing an Array of Integers 111

    Karatsuba Multiplication 113

    The Algebra Behind the Karatsuba Algorithm 119

    Summary 119

    Further Reading 120

    Practice Questions 121

    Practice Projects 122

    6 Permutations and Combinations 123

    The Terminology of Set Theory 124

    Finding All Permutations Without Repetition: A Wedding Seating Chart 126

    Getting Permutations with Nested Loops: A Less-Than-Ideal Approach 130

    Permutations with Repetition: A Password Cracker 131

    Getting K-Combinations with Recursion 134

    Get All Combinations of Balanced Parentheses 139

    Power Set: Finding All Subsets of a Set 143

    Summary 147

    Further Reading 148

    Practice Questions 148

    Practice Projects 149

    7 Memoization and Dynamic Programming 151

    Memoization 152

    Tap-Down Dynamic Programming 152

    Memoization in Functional Programming 153

    Memoizing the Recursive Fibonacci Algorithm 154

    Python's functools Module 158

    What Happens When You Memaize Impure Functions? 159

    Summary 160

    Further Reading 161

    Practice Questions 161

    8 Tail Call Optimization 163

    How Tail Recursion and Tail Call Optimization Work 164

    Accumulators in Tail Recursion 165

    Limitations of Tail Recursion 166

    Tail Recursion Case Studies 167

    Tail Recursive Reverse String 168

    Tail Recursive Find Substring 169

    Tail Recursive Exponents 169

    Tail Recursive Odd-Even 170

    Summary 172

    Further Reading 172

    Practice Questions 173

    9 Drawing Fractals 175

    Turtle Graphics 176

    Basic Turtle Functions 177

    The Sierpinski Triangle 179

    The Sierpinski Carpet 183

    Fractal Trees 187

    How Long Is the Coast of Great Britain? The Koch Curve and Snowflake 190

    The Hilbert Curve 194

    Summary 197

    Further Reading 197

    Practice Questions 197

    Practice Projects 198

    Part II Projects 201

    10 File Finder 203

    The Complete File-Search Program 204

    The Match Functions 205

    Finding the Files with an Even Number of Bytes 206

    Finding the Filenames That Contain Every Vowel 206

    The Recursive walk() Function 207

    Calling the walk() Function 208

    Useful Python Standard Library Functions for Working with Files 209

    Finding Information About the File's Name 209

    Finding Information About the File's Timestamps 210

    Modifying Your Files 212

    Summary 213

    Further Reading 213

    11 Maze Generator 215

    The Complete Maze-Generator Program 216

    Setting Up the Maze Generator's Constants 221

    Creating the Maze Data Structure 222

    Printing the Maze Data Structure 223

    Using the Recursive Backlracker Algorithm 225

    Starting the Chain of Recursive Calls 228

    Summary 229

    Further Reading 229

    12 Sliding-Tile Solver 231

    Solving 15-Puzzles Recursively 232

    The Complete Sliding-Tile Solver Program 234

    Setting Up the Program's Constants 243

    Representing the Sliding-Tile Puzzle as Data 243

    Displaying the Board 244

    Creating a New Board Data Structure 245

    Finding the Coordinates of the Blank Space 245

    Making a Move 246

    Undoing a Move 247

    Setting Up a New Puzzle 248

    Recursively Solving the Sliding-Tile Puzzle 251

    The solve() Function 251

    The attemptMove() Function 253

    Starting the Solver 255

    Summary 256

    Further Reading 257

    13 Fractal Art Maker 259

    The Built-in Fractals 260

    The Fractal Art Maker Algorithm 261

    The Complete Fractal Art Maker Program 263

    Setting Up Constants and the Turtle Configuration 267

    Working with the Shape-Drawing Functions 267

    The drawFilledSquare() Function 268

    The drawTriangleOutline() Function 270

    Using the Fractal Drawing Function 271

    Setting Up the Function 272

    Using the Specifications Dictionary 272

    Applying the Specifications 275

    Creating the Example Fractals 277

    Four Corners 277

    Spiral Squares 277

    Double Spiral Squares 278

    Triangle Spiral 278

    Conway's Game of Life Glider 278

    Sierpinski Triangle 279

    Wave 279

    Horn 279

    Snowflake 280

    Producing a Single Square or Triangle 280

    Creating Your Own Fractals 281

    Summary 282

    Further Reading 282

    14 Droste Maker 283

    Installing the Pillow Python Library 284

    Painting Your Image 285

    The Complete Droste Maker Program 286

    Setting Up 288

    Finding the Magenta Area 289

    Resizing the Base Image 291

    Recursively Placing the Image Within the Image 294

    Summary 295

    Further Reading 296

    Index 297

    From the B&N Reads Blog

    Customer Reviews