The Recursive Book of Recursion

Buy from Publisher (Free ebook!) Buy on Amazon

Ace the Coding Interview with Python and Javascript

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.

"This book takes the mystery out of recursion. By the time you finish it, you'll see recursion as a powerful technique, but also a technique usable by mere mortals."

—John D. Cook

"... this book is a worthy read for a developer who wants to deepen their knowledge of advanced programming topics. While basic recursion is included in early programming curriculum, it typically stops at examples that can be reproduced with iteration. In this book, Al Sweigart starts are these basics and quickly expands to include types of algorithms that benefit from recursion, such as tree traversal and divide-and-conquer. Though focused on those actively interviewing for engineering roles, the book is also a good fit for professional development, an engineering book club, or a brain tickler for your technical book shelf. The real life projects at the end are especially informative, which is why I think... (this review 'recurs' to the beginning)"

—Adam DuVander, @adamd, Founder of EveryDeveloper

"I have felt for a long time that I had a pretty good handle on the subject of recursion . . . Thanks to Al Sweigart's new book, I think I'm far better informed than I was before. I will re-read this book a couple more times, just to add to the knowledge."

—Ronnie Tucker, Editor, Full Circle Magazine

The Real Python Podcast episode 124 interviewed Al Sweigart about the book.

Read the Book Online

• Front Matter
• Introduction
• Chapter 1 - What Is Recursion?
• Chapter 2 - Recursion vs. Iteration
• Chapter 3 - Classic Recursion Algorithms
• Chapter 4 - Backtracking and Tree Traversal Algorithms
• Chapter 5 - Divide-and-Conquer Algorithms
• Chapter 6 - Permutations and Combinations
• Chapter 7 - Memoization and Dynamic Programming
• Chapter 8 - Tail Call Optimization
• Chapter 9 - Drawing Fractals
• Chapter 10 - File Finder
• Chapter 11 - Maze Generator
• Chapter 12 - Sliding-Tile Solver
• Chapter 13 - Fractal Art Maker
• Chapter 14 - Droste Maker

Downloads

All Source Code and Additional Content

You can view the results of the .html programs in the browser from the following links, and right-click the page and select "View Source" to see the JavaScript code. The .py files must be run on your computer with the Python interpreter. To see the execution of the Python code, copy and paste the source code to PythonTutor.com.

• ackermann_cached.py - The highly-recursive Ackermann function, with optimization.
• ackermann.html - The highly-recursive Ackermann function.
• ackermann.py - The highly-recursive Ackermann function.
• ackermannIterative.html - The highly-recursive Ackermann function, implemented without recursion.
• ackermannIterative.py - The highly-recursive Ackermann function, implemented without recursion.
• balancedParentheses.html - Detects properly balanced parentheses.
• balancedParentheses.py - Detects properly balanced parentheses.
• binarySearch.html - Searches an ordered list with the binary search algorithm.
• binarySearch.py - Searches an ordered list with the binary search algorithm.
• binarySearchIterative.html - Searches an ordered list with the binary search algorithm, without recursion.
• binarySearchIterative.py - Searches an ordered list with the binary search algorithm, without recursion.
• breakByIteration.html - Demonstrates the break keyword in a loop.
• breakByIteration.py - Demonstrates the break keyword in a loop.
• breakByRecursion.html - Simulates the break keyword with recursion.
• breakByRecursion.py - Simulates the break keyword with recursion.
• cardStack.html - Demonstrates push and pop operations with a stack.
• cardStack.py - Demonstrates push and pop operations with a stack.
• combinations.html - Generates every combination of items in a list.
• combinations.py - Generates every combination of items in a list.
• combinationsWithRepetition.py - Generates every combination (with repetition) of items in a list.
• continueByIteration.html - Demonstrates the continue keyword in a loop.
• continueByIteration.py - Demonstrates the continue keyword in a loop.
• continueByRecursion.html - Demonstrates the continue keyword with recursion.
• continueByRecursion.py - Demonstrates the continue keyword with recursion.
• depthFirstSearch.html - Depth-first search algorithm with recursion.
• depthFirstSearch.py - Depth-first search algorithm with recursion.
• depthFirstSearchIteration.py - Depth-first search algorithm with iteration.
• doNotMemoize.py - Demonstrates why you shouldn't memoize impure functions.
• drostemaker.py - Creates recursive Droste images. See Chapter 14
• drunkSierpinskiTriangle.py - Draws a "drunk" Sierpinski triangle.
• drunkSierpinskiTriangleAnimated.py - Draws an animated "drunk" Sierpinski triangle.
• examplemaze.txt - A maze file generated by the mazeGenerator program and solvable by the mazeSolver program.
• exponentByIteration.html - Calculates exponents with iteration.
• exponentByIteration.py - Calculates exponents with iteration.
• exponentByRecursion.html - Calculates exponents with recursion.
• exponentByRecursion.py - Calculates exponents with recursion.
• exponentWithPowerRule.html - Calculates exponents more efficiently.
• exponentWithPowerRule.py - Calculates exponents more efficiently.
• factorialByIteration.html - Calculates factorial with iteration.
• factorialByIteration.py - Calculates factorial with iteration.
• factorialByRecursion.html - Calculates factorial with recursion.
• factorialByRecursion.py - Calculates factorial with recursion.
• factorialEmulateRecursion.html - Calculates factorial with iteration in a way that emulates recursion.
• factorialEmulateRecursion.py - Calculates factorial with iteration in a way that emulates recursion.
• factorialTailCall.html - Calculates factorial with tail call recursion.
• factorialTailCall.py - Calculates factorial with tail call recursion.
• fibonacciByIteration.html - Calculates the Fibonacci sequence with iteration.
• fibonacciByIteration.py - Calculates the Fibonacci sequence with iteration.
• fibonacciByRecursion.html - Calculates the Fibonacci sequence with recursion.
• fibonacciByRecursion.py - Calculates the Fibonacci sequence with recursion.
• fibonacciByRecursionMemoized.html - Calculates the Fibonacci sequence with recursion and memoization.
• fibonacciByRecursionMemoized.py - Calculates the Fibonacci sequence with recursion and memoization.
• fibonacciEmulateRecursion.html - Calculates the Fibonacci sequence with iteration that emulates recursion.
• fibonacciEmulateRecursion.py - Calculates the Fibonacci sequence with iteration that emulates recursion.
• fibonacciFunctools.py - Calculates the Fibonacci sequence with Python's functools module for memoization.
• fileFinder.py - Look through folders with recursion.
• findMinValue.html - Find the smallest number in a list with recursion.
• findMinValue.py - Find the smallest number in a list with recursion.
• floodfill.html - The recursive flood fill algorithm.
• floodfill.py - The recursive flood fill algorithm.
• floodfillIterative.html - The flood fill algorithm with a loop.
• floodfillIterative.py - The flood fill algorithm with a loop.
• fractalArtMaker.py - Draws fractals. See Chapter 13.
• fractalTree.py - Draws uniform fractal trees.
• fractalTreeNonDet.py - Draws nonuniform fractal trees.
• fractalTreeNonDet2.py - Draws nonuniform fractal trees.
• functionCalls.html - Demonstrates function calls and the call stack.
• functionCalls.py - Demonstrates function calls and the call stack.
• gcdIterative.html - The GCD algorithm with iteration.
• gcdIterative.py - The GCD algorithm with iteration.
• gcdRecursive.html - The GCD algorithm with recursion
• gcdRecursive.py - The GCD algorithm with recursion
• getChangeWithMinCoins.html - Minimum coins problem.
• getChangeWithMinCoins.py - Minimum coins problem.
• getDepth.html - Calculate the depth of a tree structure.
• getDepth.py - Calculate the depth of a tree structure.
• hilbertCurve.py - Draws a Hilbert Curve.
• inorderTraversal.html - Does an in-order tree traversal.
• inorderTraversal.py - Does an in-order tree traversal.
• isEvenIterative.py - A silly iterative algorithm for determining if a number is odd or even.
• isEvenRecursive.html - A silly recursive algorithm for determining if a number is odd or even.
• isEvenRecursive.py - A silly recursive algorithm for determining if a number is odd or even.
• isOdd.html - A silly recursive algorithm for determining if a number is odd or even.
• isOdd.py - A silly recursive algorithm for determining if a number is odd or even.
• karatsubaMultiplication.html - Karatsuba algorithm for multiplication.
• karatsubaMultiplication.py - Karatsuba algorithm for multiplication.
• kochSnowflake.py - Draws a Koch Snowflake.
• localVariables.html - Demonstrates how local variables work.
• localVariables.py - Demonstrates how local variables work.
• loopsByIteration.html - Demonstrates a loop.
• loopsByIteration.py - Demonstrates a loop.
• loopsByRecursion.html - Demonstrates a loop done with recursion.
• loopsByRecursion.py - Demonstrates a loop done with recursion.
• mazeGenerator.html - Generates a maze with the recursive backtracking algorithm.
• mazeGenerator.py - Generates a maze with the recursive backtracking algorithm.
• mazeSolver.html - Solves mazes recursively.
• mazeSolver.py - Solves mazes recursively.
• mergeSort.html - Recursive merge sort algorithm.
• mergeSort.py - Recursive merge sort algorithm.
• museum-recursive.p/recursion/ng - Recursive image used in drostemaker.py program.
• museum.png - Original image used in drostemaker.py program.
• nestedLoopPermutations.html - Permutations calculated with nested loops.
• nestedLoopPermutations.py - Permutations calculated with nested loops.
• nestedLoopsByIteration.html - Demonstration of nested loops.
• nestedLoopsByIteration.py - Demonstration of nested loops.
• nestedLoopsByRecursion.html - Demonstration of nested loops simulated with recursion.
• nestedLoopsByRecursion.py - Demonstration of nested loops simulated with recursion.
• nQueens.py - N Queens problem solved with recursion.
• nQueensPermutation.py - N Queens problem solved with recursive permutations algorithm.
• palindrome.html - Palindrome detection with recursion.
• palindrome.py - Palindrome detection with recursion.
• permutations.html - Calculating permutations with recursion.
• permutations.py - Calculating permutations with recursion.
• permutationsWithRepetition.html - Calculating permutations (with repetition) with recursion.
• permutationsWithRepetition.py - Calculating permutations (with repetition) with recursion.
• postorderTraversal.html - Post-order tree traversal.
• postorderTraversal.py - Post-order tree traversal.
• powerSet.html - Calculating power sets recursively.
• powerSet.py - Calculating power sets recursively.
• powerSetCombinations.html - Calculating power sets with the recursive combination algorithm in combinations.py.
• powerSetCombinations.py - Calculating power sets with the recursive combination algorithm in combinations.py.
• preorderTraversal.html - Pre-order tree traversal.
• preorderTraversal.py - Pre-order tree traversal.
• quickselect.py - Uses the quickselect algorithm to find an item in an unsorted list.
• quicksort.html - Recursive quicksort algorithm.
• quicksort.py - Recursive quicksort algorithm.
• reverseString.html - Recursive algorithm to reverse a string.
• reverseString.py - Recursive algorithm to reverse a string.
• reverseStringTailCall.html - Tail recursive algorithm to reverse a string.
• reverseStringTailCall.py - Tail recursive algorithm to reverse a string.
• shortest.html - The shortest possible recursive function.
• shortest.py - The shortest possible recursive function.
• shortestWithBaseCase.html - The shortest possible recursive function with a base case.
• shortestWithBaseCase.py - The shortest possible recursive function with a base case.
• sierpinskiCarpet.py - Draws a Sierpiński Carpet.
• sierpinskiTriangle.py - Draws a Sierpiński Triangle.
• slidingtilesolver-withcache.py - Solves the 15 tile slide puzzle with recursion and memoization.
• slidingTileSolver.html - Solves the 15 tile slide puzzle with recursion.
• slidingTileSolver.py - Solves the 15 tile slide puzzle with recursion.
• spiral.py - Draws a spiral as a demonstration of Python's turtle module.
• stackMath.py - Carrying out math operations using a stack.
• stairClimbing.py - Counts the number of ways to climb a set of stairs taking 1, 2, or 3 steps at a time.
• sumAccumulator.html - Addition using recursion and an accumulator argument.
• sumAccumulator.py - Addition using recursion and an accumulator argument.
• sumDivConq.html - Addition using a divide-and-conquer algorithm.
• sumDivConq.py - Addition using a divide-and-conquer algorithm.
• sumHeadTail.html - Addition using a head-tail approach.
• sumHeadTail.py - Addition using a head-tail approach.
• towerOfHanoiSolver_iterative.py - A Tower of Hanoi solver that doesn't use recursion.
• towerOfHanoiSolver.html - A recursive Tower of Hanoi solver.
• towerOfHanoiSolver.py - A recursive Tower of Hanoi solver.