Introduction

The programming technique of recursion can produce elegant code solutions. More often, however, it produces confused programmers. This doesn’t mean programmers can (or should) ignore recursion. Despite its reputation for being challenging, recursion is an important computer science topic and can yield keen insights into programming itself. At the very least, knowing recursion can help you nail a coding job interview.

If you’re a student with an interest in computer science, recursion is a necessary hurdle you’ll have to overcome to understand many popular algorithms. If you’re a programming bootcamp graduate or self-taught programmer who managed to bypass the more theoretical computer science topics, recursion problems are still sure to come up during whiteboard coding interviews. And if you’re an experienced software engineer who has never touched a recursive algorithm before, you might find recursion to be an embarrassing gap in your knowledge.

There’s no need to worry. Recursion isn’t as hard to understand as it is to teach. As I’ll explain in Chapter 1, I attribute the widespread misunderstanding of recursion to poor instruction rather than any inherent difficulty. And since recursive functions aren’t commonly used in day-to-day programming, many folks get along just fine without them.

But a certain conceptual beauty lies behind recursive algorithms that can aid your understanding of programming even if you don’t often apply them. Recursion has a visual beauty as well. The technique is behind the amazing mathematical art of fractals, the self-similar shapes shown in Figure 1.

However, this book is not entirely in praise of recursion. I include some sharp criticisms of this technique. Recursion is overused in cases where a simpler solution exists. Recursive algorithms can be hard to understand, have worse performance, and are susceptible to crash-causing stack overflow errors. And a certain kind of programmer may use recursion not because it’s the right technique for a given problem, but simply because they feel smarter when they write code that other programmers struggle to understand. Computer scientist Dr. John Wilander once said, “When you finish a PhD in computer science, they take you to a special room and explain that you must never use recursion in real life. Its only purpose is to make programming hard for undergrads.”

So, whether you want to get an edge in coding interviews, you want to create beautiful mathematical art, or you stubbornly seek to finally understand the intriguing properties of this concept, this book will be your guide down the rabbit hole that is recursion (and the rabbit holes within that rabbit hole). Recursion is one of the computer science topics that separates the professionals from the beginners. By reading this book, you’ll master a great skill and learn its dark secret: recursion isn’t as complicated as people think it is.

Who Is This Book For?

This book is for those who are intimidated or intrigued by recursive algorithms. Recursion is one of those topics that seems like black magic to beginner programmers or freshman computer science students. Most recursion lessons are hard to follow and make the subject seem frustrating, even fearsome. For these readers, I hope this book’s direct explanations and ample examples can help make the topic finally click.

The only prerequisite for this book is basic programming experience with either the Python or JavaScript programming languages, which the chapters’ code examples use. The book’s programs have been stripped down to their essences; if you know how to call and create functions and the difference between global and local variables, you know enough to work through the programming examples.

About This Book

This book has 14 chapters:

Part I: Understanding Recursion

1. Chapter 1: What Is Recursion? Explains recursion and how it is the natural result of the way programming languages implement functions and function calls. This chapter also argues that recursion isn’t nearly the elegant, mystical concept many claim it is.
2. Chapter 2: Recursion vs. Iteration Dives into the differences (and many similarities) between recursive and iterative techniques.
3. Chapter 3: Classic Recursion Algorithms Covers famous recursive programs such as the Tower of Hanoi, the flood fill algorithm, and others.
4. Chapter 4: Backtracking and Tree Traversal Algorithms Discusses a problem for which recursion is particularly suited: traversing tree data structures, such as when solving mazes and navigating a directory.
5. Chapter 5: Divide-and-Conquer Algorithms Discusses how recursion is useful for splitting large problems into smaller subproblems and covers several common divide-and-conquer algorithms.
6. Chapter 6: Permutations and Combinations Covers recursive algorithms involving ordering and matching, as well as the common programming problems to which these techniques are applied.
7. Chapter 7: Memoization and Dynamic Programming Explains some simple tricks to improve code efficiency when applying recursion in the real world.
8. Chapter 8: Tail Call Optimization Covers tail call optimization, a common technique used to improve the performance of recursive algorithms, and how it works.
9. Chapter 9: Drawing Fractals Tours the intriguing art that can be programmatically produced by recursive algorithms. This chapter makes use of turtle graphics for generating its images.

Part II: Projects

1. Chapter 10: File Finder Covers a project that searches through the files on your computer according to custom search parameters you provide.
2. Chapter 11: Maze Generator Covers a project that automatically generates mazes of any size using the recursive backtracker algorithm.
3. Chapter 12: Sliding-Tile Solver Covers a project that solves sliding-tile puzzles, also called 15-puzzles.
4. Chapter 13: Fractal Art Maker Explores a project that can produce custom fractal art of your own design.
5. Chapter 14: Droste Maker Explores a project that produces recursive, picture-in-picture images using the Pillow image-manipulation module.

Hands-On, Experimental Computer Science

Reading about recursion won’t teach you how to implement it on its own. This book includes many recursive code examples in both the Python and JavaScript programming languages for you to experiment with. If you’re new to programming, you can read my book Automate the Boring Stuff with Python, 2nd edition (No Starch Press, 2019), or Python Crash Course, 2nd edition, by Eric Matthes (No Starch Press, 2019) for an introduction to both programming and the Python programming language.

I recommend stepping through these programs with a debugger. A debugger lets you execute programs one line at a time and inspect the state of the program along the way, allowing you to pinpoint where bugs occur. Chapter 11 of Automate the Boring Stuff with Python, 2nd edition, covers how to use the Python debugger and is free to read online at https://automatetheboringstuff.com/2e/chapter11.

The chapters in this book display the Python and JavaScript code examples together. The Python code is saved in a .py file, and the JavaScript code in an .html file (not a .js file). For example, take the following hello.py file:

print('Hello, world!')

And the following hello.html file:

<script type="text/javascript">
document.write("Hello, world!<br />");
</script>

The two code listings act as a Rosetta stone, describing programs that produce the same results in two different languages.

I encourage you to manually copy these programs by using your keyboard, rather than simply copying and pasting their source code into a new file. This helps your “muscle memory” of the programs and forces you to consider each line as you type it.

The .html files are technically not valid because they’re missing several necessary HTML tags, such as <html> and <body>, but your browser will still be able to display the output. These tags have been left out on purpose. The programs in this book are written for simplicity and readability, not to demonstrate web development best practices.

Installing Python

While every computer has a web browser that can view the .html files in this book, you must install Python separately if you wish to run the book’s Python code. You can download Python for Microsoft Windows, Apple macOS, and Ubuntu Linux for free from https://python.org/downloads. Be sure to download a version of Python 3 (such as 3.10) and not Python 2. Python 3 made a few backward-incompatible changes to the language, and the programs in this book may not run correctly, if at all, on Python 2.

Running IDLE and the Python Code Examples

You can use the IDLE editor that comes with Python to write your Python code or install a free editor, such as the Mu Editor from https://codewith.mu, PyCharm Community Edition from https://www.jetbrains.com/pycharm/download, or Microsoft Visual Studio Code from https://code.visualstudio.com/Download.

To open IDLE on Windows, open the Start menu in the lower-left corner of your screen, enter IDLE in the search box, and select IDLE (Python 3.10 64-bit).

On macOS, open the Finder window and click Applications▶Python 3.10, and then the IDLE icon.

On Ubuntu, select Applications▶Accessories▶Terminal and then enter IDLE 3. You may also be able to click Applications at the top of the screen, select Programming, and then click IDLE 3.

IDLE has two types of windows. The interactive shell window has the >>> prompt and is used for running Python instructions one at a time. This is useful when you want to experiment with bits of Python code. The file editor window is where you can enter full Python programs and save them as .py files. This is how you’ll enter the source code for the Python programs in this book. To open a new file editor window, click File▶New File. You can run the programs by clicking Run▶Run Module or pressing F5.

Running the JavaScript Code Examples in the Browser

Your computer’s web browser can run the JavaScript programs and display their output, but to write JavaScript code, you’ll need a text editor. A simple program like Notepad or TextMate will do, but you can also install text editors specifically for writing code, such as IDLE or Sublime Text from https://www.sublimetext.com.

After typing the code for your JavaScript programs, save the files as .html files, not .js files. Open them in a web browser to view the results. Any modern web browser works for this purpose.