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.
Author(s): Al Sweigart
Edition: 1
Publisher: No Starch Press
Year: 2022
Language: English
Commentary: Vector PDF
Pages: 328
City: San Francisco, CA
Tags: Algorithms; Data Structures; Python; JavaScript; Recursion; Dynamic Programming; Fractals; Combinatorics; Backtracking; Trees; Divide and Conquer Algorithms; Recursive Algorithms; Memoization; Maze Generation; Elementary; Tail Call Optimization
Brief Contents
Contents in Detail
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
