The Recursive Book of Recursion

The Recursive Book of Recursion

by Al Sweigart
Released August 2022
Publisher(s): No Starch Press
ISBN: 9781718502024

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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.

Table of contents

  1. Title Page
  2. Copyright
  3. Dedication
  4. About the Author
  5. Foreword
  6. Acknowledgments
  7. Introduction
    1. Who Is This Book For?
    2. About This Book
    3. Hands-On, Experimental Computer Science
      1. Installing Python
      2. Running IDLE and the Python Code Examples
      3. Running the JavaScript Code Examples in the Browser
  8. Part I: Understanding Recursion
    1. Chapter 1: What Is Recursion?
      1. The Definition of Recursion
      2. What Are Functions?
      3. What Are Stacks?
      4. What Is the Call Stack?
      5. What Are Recursive Functions and Stack Overflows?
      6. Base Cases and Recursive Cases
      7. Code Before and After the Recursive Call
      8. Summary
      9. Further Reading
      10. Practice Questions
    2. Chapter 2: Recursion vs. Iteration
      1. Calculating Factorials
        1. The Iterative Factorial Algorithm
        2. The Recursive Factorial Algorithm
        3. Why the Recursive Factorial Algorithm Is Terrible
      2. Calculating the Fibonacci Sequence
        1. The Iterative Fibonacci Algorithm
        2. The Recursive Fibonacci Algorithm
        3. Why the Recursive Fibonacci Algorithm Is Terrible
      3. Converting a Recursive Algorithm into an Iterative Algorithm
      4. Converting an Iterative Algorithm into a Recursive Algorithm
      5. Case Study: Calculating Exponents
        1. Creating a Recursive Exponents Function
        2. Creating an Iterative Exponents Function Based on Recursive Insights
      6. When Do You Need to Use Recursion?
      7. Coming Up with Recursive Algorithms
      8. Summary
      9. Further Reading
      10. Practice Questions
      11. Practice Projects
    3. Chapter 3: Classic Recursion Algorithms
      1. Summing Numbers in an Array
      2. Reversing a String
      3. Detecting Palindromes
      4. Solving the Tower of Hanoi
      5. Using Flood Fill
      6. Using the Ackermann Function
      7. Summary
      8. Further Reading
      9. Practice Questions
      10. Practice Projects
    4. Chapter 4: Backtracking and Tree Traversal Algorithms
      1. Using Tree Traversal
        1. A Tree Data Structure in Python and JavaScript
        2. Traversing the Tree
        3. Preorder Tree Traversal
        4. Postorder Tree Traversal
        5. Inorder Tree Traversal
      2. Finding Eight-Letter Names in a Tree
      3. Getting the Maximum Tree Depth
      4. Solving Mazes
      5. Summary
      6. Further Reading
      7. Practice Questions
      8. Practice Projects
    5. Chapter 5: Divide-and-Conquer Algorithms
      1. Binary Search: Finding a Book in an Alphabetized Bookshelf
      2. Quicksort: Splitting an Unsorted Pile of Books into Sorted Piles
      3. Merge Sort: Merging Small Piles of Playing Cards into Larger Sorted Piles
      4. Summing an Array of Integers
      5. Karatsuba Multiplication
      6. The Algebra Behind the Karatsuba Algorithm
      7. Summary
      8. Further Reading
      9. Practice Questions
      10. Practice Projects
    6. Chapter 6: Permutations and Combinations
      1. The Terminology of Set Theory
      2. Finding All Permutations Without Repetition: A Wedding Seating Chart
      3. Getting Permutations with Nested Loops: A Less-Than-Ideal Approach
      4. Permutations with Repetition: A Password Cracker
      5. Getting K-Combinations with Recursion
      6. Get All Combinations of Balanced Parentheses
      7. Power Set: Finding All Subsets of a Set
      8. Summary
      9. Further Reading
      10. Practice Questions
      11. Practice Projects
    7. Chapter 7: Memoization and Dynamic Programming
      1. Memoization
        1. Top-Down Dynamic Programming
        2. Memoization in Functional Programming
        3. Memoizing the Recursive Fibonacci Algorithm
      2. Python’s functools Module
      3. What Happens When You Memoize Impure Functions?
      4. Summary
      5. Further Reading
      6. Practice Questions
    8. Chapter 8: Tail Call Optimization
      1. How Tail Recursion and Tail Call Optimization Work
      2. Accumulators in Tail Recursion
      3. Limitations of Tail Recursion
      4. Tail Recursion Case Studies
        1. Tail Recursive Reverse String
        2. Tail Recursive Find Substring
        3. Tail Recursive Exponents
        4. Tail Recursive Odd-Even
      5. Summary
      6. Further Reading
      7. Practice Questions
    9. Chapter 9: Drawing Fractals
      1. Turtle Graphics
      2. Basic Turtle Functions
      3. The Sierpiński Triangle
      4. The Sierpiński Carpet
      5. Fractal Trees
      6. How Long Is the Coast of Great Britain? The Koch Curve and Snowflake
      7. The Hilbert Curve
      8. Summary
      9. Further Reading
      10. Practice Questions
      11. Practice Projects
  9. Part II: Projects
    1. Chapter 10: File Finder
      1. The Complete File-Search Program
      2. The Match Functions
        1. Finding the Files with an Even Number of Bytes
        2. Finding the Filenames That Contain Every Vowel
      3. The Recursive walk() Function
      4. Calling the walk() Function
      5. Useful Python Standard Library Functions for Working with Files
        1. Finding Information About the File’s Name
        2. Finding Information About the File’s Timestamps
        3. Modifying Your Files
      6. Summary
      7. Further Reading
    2. Chapter 11: Maze Generator
      1. The Complete Maze-Generator Program
      2. Setting Up the Maze Generator’s Constants
      3. Creating the Maze Data Structure
      4. Printing the Maze Data Structure
      5. Using the Recursive Backtracker Algorithm
      6. Starting the Chain of Recursive Calls
      7. Summary
      8. Further Reading
    3. Chapter 12: Sliding-Tile Solver
      1. Solving 15-Puzzles Recursively
      2. The Complete Sliding-Tile Solver Program
      3. Setting Up the Program’s Constants
      4. Representing the Sliding-Tile Puzzle as Data
        1. Displaying the Board
        2. Creating a New Board Data Structure
        3. Finding the Coordinates of the Blank Space
        4. Making a Move
        5. Undoing a Move
      5. Setting Up a New Puzzle
      6. Recursively Solving the Sliding-Tile Puzzle
        1. The solve() Function
        2. The attemptMove() Function
      7. Starting the Solver
      8. Summary
      9. Further Reading
    4. Chapter 13: Fractal Art Maker
      1. The Built-in Fractals
      2. The Fractal Art Maker Algorithm
      3. The Complete Fractal Art Maker Program
      4. Setting Up Constants and the Turtle Configuration
      5. Working with the Shape-Drawing Functions
        1. The drawFilledSquare() Function
        2. The drawTriangleOutline() Function
      6. Using the Fractal Drawing Function
        1. Setting Up the Function
        2. Using the Specifications Dictionary
        3. Applying the Specifications
      7. Creating the Example Fractals
        1. Four Corners
        2. Spiral Squares
        3. Double Spiral Squares
        4. Triangle Spiral
        5. Conway’s Game of Life Glider
        6. Sierpiński Triangle
        7. Wave
        8. Horn
        9. Snowflake
        10. Producing a Single Square or Triangle
      8. Creating Your Own Fractals
      9. Summary
      10. Further Reading
    5. Chapter 14: Droste Maker
      1. Installing the Pillow Python Library
      2. Painting Your Image
      3. The Complete Droste Maker Program
      4. Setting Up
      5. Finding the Magenta Area
      6. Resizing the Base Image
      7. Recursively Placing the Image Within the Image
      8. Summary
      9. Further Reading
  10. Index

Product information

  • Title: The Recursive Book of Recursion
  • Author(s): Al Sweigart
  • Release date: August 2022
  • Publisher(s): No Starch Press
  • ISBN: 9781718502024