Al Sweigart - The Recursive Book of Recursion

by Al Sweigart

THE RECURSIVE BOOK OF RECURSION. Copyright 2022 by Al Sweigart.

Some rights reserved. This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/us or send a letter to Creative Commons, PO Box 1866, Mountain View, CA 94042, USA.

First printing
26 25 24 23 22 1 2 3 4 5

ISBN-13: 978-1-71850-202-4 (print)
ISBN-13: 978-1-71850-203-1 (ebook)

Publisher: William Pollock
Production Manager: Rachel Monaghan
Production Editor: Miles Bond
Developmental Editor: Frances Saux
Cover Illustrator: James L. Barry
Interior Design: Octopod Studios
Technical Reviewer: Sarah Kuchinsky
Copyeditor: Sharon Wilkey
Compositor: Maureen Forys, Happenstance Type-O-Rama
Proofreader: Audrey Doyle

For information on distribution, bulk sales, corporate sales, or translations, please contact No Starch Press, Inc. directly at info@nostarch.com or:

No Starch Press, Inc.
245 8th Street, San Francisco, CA 94103
phone: 1.415.863.9900
www.nostarch.com

Library of Congress Cataloging-in-Publication Data

Library of Congress Control Number: 2022932456

No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark.

The information in this book is distributed on an As Is basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it.

To Jack, who held up a mirror in front of my mirror

Al Sweigart is a software developer, fellow of the Python Software Foundation, and author of several programming books with No Starch Press, including the worldwide bestseller Automate the Boring Stuff with Python. His Creative Commons licensed works are available at https://www.inventwithpython.com.

Sarah Kuchinsky, MS, is a corporate trainer and consultant. She uses Python for a variety of applications, including health systems modeling, game development, and task automation. Sarah is a co-founder of the North Bay Python conference, tutorials chair for PyCon US, and lead organizer for PyLadies Silicon Valley. She holds degrees in management science as well as in engineering and mathematics.

When I was approached by Al to write the foreword to this book, I was pretty excited about the prospect. A book on recursion! Now, thats something you just dont see every day. Considered by many to be one of the more mysterious topics in programming, recursion is often discouraged. Oddly, this stands in stark contrast to its storied use in weird job interview questions.

However, there are all sorts of practical reasons to learn about recursion. Recursive thinking is very much a mindset about problem-solving. At its core, larger problems get broken into smaller problems. And sometimes along the way, hard problems are rewritten into equivalent but easier-to-solve simple problems. This sort of thinking can be a useful tool when applied to software designeven when recursion is not being used. Thus, its a worthy topic of study for programmers of all skill levels.

In my unbridled excitement to say more about recursion, I originally wrote this foreword in the form of a few short stories involving friends whod applied recursive thinking in different ways but achieved a similar result. First there was the story of Ben, who learned about recursion, took it too far, and somehow managed to disappear off the face of the earth under mysterious circumstances after committing the following Python code into production:

Then there was the story of Chelsea, who became so effective at real-world problem-solving that she was promptly fired! Oh, you wouldnt believe how much all the fine editors at No Starch (bless their hearts) hated these stories. You cant start a book by telling people stories like that. Its just going to scare everyone away! To be fair, they probably have a point. In fact, they even made me move a more reassuring paragraph about recursion from later in this foreword up to the second paragraph just so you wouldnt first read about the stories of Ben and Chelsea and run away in a screaming horror to read a book about design patterns instead.

Clearly, writing the foreword to a book is serious business. So, regrettably, Ill have to share the true stories of Ben and Chelsea with you another time. But, getting back to the book, its true that recursion is not a technique that gets applied to the vast majority of problems in day-to-day programming. As such, it often carries an aura of magic about it. This book hopes to dispel much of that. This is a good thing.

Finally, as you set off on your recursion journey, be prepared to have your brain bent in new directions. Not to worrythis is normal! However, its also important to stress that recursion is supposed to be a bit of fun. Well, at least a little bit. So, enjoy the ride!

David Beazley

Author of Python Cookbook and Python Distilled

Teacher of aspiring problem solvers

https://www.dabeaz.com

Its misleading to have only my name on the cover. Id like to thank my publisher, Bill Pollock; my editor, Frances Saux; my technical reviewer, Sarah Kuchinsky; my production editor, Miles Bond; the production manager, Rachel Monaghan; and the rest of the staff at No Starch Press for their invaluable help.

Finally, I would like to thank my family, friends, and readers for all their suggestions and support.

The programming technique of recursion can produce elegant code solutions. More often, however, it produces confused programmers. This doesnt 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 youre a student with an interest in computer science, recursion is a necessary hurdle youll have to overcome to understand many popular algorithms. If youre 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 youre an experienced software engineer who has never touched a recursive algorithm before, you might find recursion to be an embarrassing gap in your knowledge.