book

The Recursive Book of Recursion

Name: The Recursive Book of Recursion
Author: Al Sweigart
ISBN: 9781718502024

by Al Sweigart

August 2022

Intermediate to advanced

328 pages

8h 9m

English

No Starch Press

Read now

Unlock full access

Title Page
Copyright
Dedication
About the Author
Foreword
Acknowledgments
Introduction
Who Is This Book For?About This BookHands-On, Experimental Computer ScienceInstalling PythonRunning IDLE and the Python Code ExamplesRunning the JavaScript Code Examples in the Browser
Part I: Understanding Recursion
Chapter 1: What Is Recursion?
The Definition of RecursionWhat Are Functions?What Are Stacks?What Is the Call Stack?What Are Recursive Functions and Stack Overflows?Base Cases and Recursive CasesCode Before and After the Recursive CallSummaryFurther ReadingPractice Questions
Chapter 2: Recursion vs. Iteration
Calculating FactorialsThe Iterative Factorial AlgorithmThe Recursive Factorial AlgorithmWhy the Recursive Factorial Algorithm Is TerribleCalculating the Fibonacci SequenceThe Iterative Fibonacci AlgorithmThe Recursive Fibonacci AlgorithmWhy the Recursive Fibonacci Algorithm Is TerribleConverting a Recursive Algorithm into an Iterative AlgorithmConverting an Iterative Algorithm into a Recursive AlgorithmCase Study: Calculating ExponentsCreating a Recursive Exponents FunctionCreating an Iterative Exponents Function Based on Recursive InsightsWhen Do You Need to Use Recursion?Coming Up with Recursive AlgorithmsSummaryFurther ReadingPractice QuestionsPractice Projects

Chapter 3: Classic Recursion Algorithms
Summing Numbers in an ArrayReversing a StringDetecting PalindromesSolving the Tower of HanoiUsing Flood FillUsing the Ackermann FunctionSummaryFurther Reading Practice QuestionsPractice Projects
Chapter 4: Backtracking and Tree Traversal Algorithms
Using Tree TraversalA Tree Data Structure in Python and JavaScriptTraversing the TreePreorder Tree TraversalPostorder Tree TraversalInorder Tree TraversalFinding Eight-Letter Names in a TreeGetting the Maximum Tree DepthSolving MazesSummaryFurther ReadingPractice QuestionsPractice Projects
Chapter 5: Divide-and-Conquer Algorithms
Binary Search: Finding a Book in an Alphabetized BookshelfQuicksort: Splitting an Unsorted Pile of Books into Sorted PilesMerge Sort: Merging Small Piles of Playing Cards into Larger Sorted PilesSumming an Array of IntegersKaratsuba MultiplicationThe Algebra Behind the Karatsuba AlgorithmSummaryFurther ReadingPractice QuestionsPractice Projects
Chapter 6: Permutations and Combinations
The Terminology of Set TheoryFinding All Permutations Without Repetition: A Wedding Seating ChartGetting Permutations with Nested Loops: A Less-Than-Ideal ApproachPermutations with Repetition: A Password CrackerGetting K-Combinations with RecursionGet All Combinations of Balanced ParenthesesPower Set: Finding All Subsets of a SetSummaryFurther ReadingPractice QuestionsPractice Projects
Chapter 7: Memoization and Dynamic Programming
MemoizationTop-Down Dynamic ProgrammingMemoization in Functional ProgrammingMemoizing the Recursive Fibonacci AlgorithmPython’s functools ModuleWhat Happens When You Memoize Impure Functions?SummaryFurther ReadingPractice Questions
Chapter 8: Tail Call Optimization
How Tail Recursion and Tail Call Optimization WorkAccumulators in Tail RecursionLimitations of Tail RecursionTail Recursion Case StudiesTail Recursive Reverse StringTail Recursive Find SubstringTail Recursive ExponentsTail Recursive Odd-EvenSummaryFurther ReadingPractice Questions
Chapter 9: Drawing Fractals
Turtle GraphicsBasic Turtle FunctionsThe Sierpiński TriangleThe Sierpiński CarpetFractal TreesHow Long Is the Coast of Great Britain? The Koch Curve and SnowflakeThe Hilbert CurveSummaryFurther ReadingPractice QuestionsPractice Projects
Part II: Projects
Chapter 10: File Finder
The Complete File-Search ProgramThe Match FunctionsFinding the Files with an Even Number of BytesFinding the Filenames That Contain Every VowelThe Recursive walk() FunctionCalling the walk() FunctionUseful Python Standard Library Functions for Working with FilesFinding Information About the File’s NameFinding Information About the File’s TimestampsModifying Your FilesSummaryFurther Reading
Chapter 11: Maze Generator
The Complete Maze-Generator ProgramSetting Up the Maze Generator’s ConstantsCreating the Maze Data StructurePrinting the Maze Data StructureUsing the Recursive Backtracker AlgorithmStarting the Chain of Recursive CallsSummaryFurther Reading
Chapter 12: Sliding-Tile Solver
Solving 15-Puzzles RecursivelyThe Complete Sliding-Tile Solver ProgramSetting Up the Program’s ConstantsRepresenting the Sliding-Tile Puzzle as DataDisplaying the BoardCreating a New Board Data StructureFinding the Coordinates of the Blank SpaceMaking a MoveUndoing a MoveSetting Up a New PuzzleRecursively Solving the Sliding-Tile PuzzleThe solve() FunctionThe attemptMove() FunctionStarting the SolverSummaryFurther Reading
Chapter 13: Fractal Art Maker
The Built-in FractalsThe Fractal Art Maker AlgorithmThe Complete Fractal Art Maker ProgramSetting Up Constants and the Turtle ConfigurationWorking with the Shape-Drawing FunctionsThe drawFilledSquare() FunctionThe drawTriangleOutline() FunctionUsing the Fractal Drawing FunctionSetting Up the FunctionUsing the Specifications DictionaryApplying the Specifications Creating the Example FractalsFour CornersSpiral SquaresDouble Spiral SquaresTriangle SpiralConway’s Game of Life GliderSierpiński TriangleWaveHornSnowflakeProducing a Single Square or TriangleCreating Your Own FractalsSummaryFurther Reading
Chapter 14: Droste Maker
Installing the Pillow Python LibraryPainting Your ImageThe Complete Droste Maker ProgramSetting UpFinding the Magenta AreaResizing the Base ImageRecursively Placing the Image Within the ImageSummaryFurther Reading
Index

Content preview from The Recursive Book of Recursion

4 Backtracking and Tree Traversal Algorithms

In previous chapters, you learned that recursion is especially suited for problems that involve a tree-like structure and backtracking, such as maze-solving algorithms. To see why, consider that a tree’s trunk splits off into multiple branches. Those branches themselves split off into other branches. In other words, a tree has a recursive, self-similar shape.

A maze can be represented by a tree data structure, since mazes branch off into different paths, which in turn branch off into more paths. When you reach a dead end in a maze, you must backtrack to an earlier branching point.

The task of ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781098141356Errata Page

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

The Recursive Book of Recursion

by Al Sweigart

4 Backtracking and Tree Traversal Algorithms

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.