The Recursive Book of Recursion

Recursion, and recursive algorithms, have a reputation for being intimidating. They're seen as an advanced computer science topic often brought up in coding interviews. Moreover, coders often perceive the use of a recursive algorithm as a sophisticated solution that only true programmers can produce. But there's nothing magical about recursion. Its fearsome reputation is more a product of poor teaching than of the complexity of recursion itself.

This book teaches the basics of recursion, exposes the ways it's often poorly taught, and clarifies the fundamental principles behind all recursive algorithms. It is project-based, containing complete, runnable programs in both Python and JavaScript, and covers several common recursive algorithms for tasks like calculating factorials, producing numbers in the Fibonacci sequence, tree traversal, maze solving, binary search, quicksort and merge sort, Karatsuba multiplication, permutations and combinations, and solving the eight queens problem.

The book also explains tail call optimization and memoization, concepts often employed to produce effective recursive algorithms, and the call stack, which is a critical part of how recursive functions work but is almost never explicitly pointed out in lessons on recursion. The last chapter, on fractals, culminates with examples of the beautiful fractal shapes recursion can produce.

Title: The Recursive Book of Recursion
Subtitle: Ace the Coding Interview with Python and Javascript
Publisher: No Starch Press
Author(s): Al Sweigart
Published: 2022-07-21
Edition: 1
Format: eBook (pdf, epub, mobi)
Pages: 174
Language: English
ISBN-10: 1718502028
ISBN-13: 9781718502024
License: Read online for free
Book Homepage: Free eBook, Errata, Code, Solutions, etc.

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