Contents In Detail

  1. Title Page
  2. Copyright
  3. Dedication
  4. About the Author
  5. Foreword
  6. Acknowledgments
  7. Introduction
    1. Who Is This Book For?
    2. About This Book
    3. Hands-On, Experimental Computer Science
      1. Installing Python
      2. Running IDLE and the Python Code Examples
      3. Running the JavaScript Code Examples in the Browser
  8. Part I: Understanding Recursion
    1. Chapter 1: What Is Recursion?
      1. The Definition of Recursion
      2. What Are Functions?
      3. What Are Stacks?
      4. What Is the Call Stack?
      5. What Are Recursive Functions and Stack Overflows?
      6. Base Cases and Recursive Cases
      7. Code Before and After the Recursive Call
      8. Summary
      9. Further Reading
      10. Practice Questions
    2. Chapter 2: Recursion vs. Iteration
      1. Calculating Factorials
        1. The Iterative Factorial Algorithm
        2. The Recursive Factorial Algorithm
        3. Why the Recursive Factorial Algorithm Is Terrible
      2. Calculating the Fibonacci Sequence
        1. The Iterative Fibonacci Algorithm
        2. The Recursive Fibonacci Algorithm
        3. Why the Recursive Fibonacci Algorithm Is Terrible
      3. Converting a Recursive Algorithm into an Iterative Algorithm
      4. Converting an Iterative Algorithm into a Recursive Algorithm
      5. Case Study: Calculating Exponents
        1. Creating a Recursive Exponents Function
        2. Creating an Iterative Exponents Function Based on Recursive Insights
      6. When Do You Need to Use Recursion?
      7. Coming Up with Recursive Algorithms
      8. Summary
      9. Further Reading
      10. Practice Questions
      11. Practice Projects
    3. Chapter 3: Classic Recursion Algorithms
      1. Summing Numbers in an Array
      2. Reversing a String
      3. Detecting Palindromes
      4. Solving the Tower of Hanoi
      5. Using Flood Fill
      6. Using the Ackermann Function
      7. Summary
      8. Further Reading
      9. Practice Questions
      10. Practice Projects
    4. Chapter 4: Backtracking and Tree Traversal Algorithms
      1. Using Tree Traversal
        1. A Tree Data Structure in Python and JavaScript
        2. Traversing the Tree
        3. Preorder Tree Traversal
        4. Postorder Tree Traversal
        5. Inorder Tree Traversal
      2. Finding Eight-Letter Names in a Tree
      3. Getting the Maximum Tree Depth
      4. Solving Mazes
      5. Summary
      6. Further Reading
      7. Practice Questions
      8. Practice Projects
    5. Chapter 5: Divide-and-Conquer Algorithms
      1. Binary Search: Finding a Book in an Alphabetized Bookshelf
      2. Quicksort: Splitting an Unsorted Pile of Books into Sorted Piles
      3. Merge Sort: Merging Small Piles of Playing Cards into Larger Sorted Piles
      4. Summing an Array of Integers
      5. Karatsuba Multiplication
      6. The Algebra Behind the Karatsuba Algorithm
      7. Summary
      8. Further Reading
      9. Practice Questions
      10. Practice Projects
    6. Chapter 6: Permutations and Combinations
      1. The Terminology of Set Theory
      2. Finding All Permutations Without Repetition: A Wedding Seating Chart
      3. Getting Permutations with Nested Loops: A Less-Than-Ideal Approach
      4. Permutations with Repetition: A Password Cracker
      5. Getting K-Combinations with Recursion
      6. Get All Combinations of Balanced Parentheses
      7. Power Set: Finding All Subsets of a Set
      8. Summary
      9. Further Reading
      10. Practice Questions
      11. Practice Projects
    7. Chapter 7: Memoization and Dynamic Programming
      1. Memoization
        1. Top-Down Dynamic Programming
        2. Memoization in Functional Programming
        3. Memoizing the Recursive Fibonacci Algorithm
      2. Python’s functools Module
      3. What Happens When You Memoize Impure Functions?
      4. Summary
      5. Further Reading
      6. Practice Questions
    8. Chapter 8: Tail Call Optimization
      1. How Tail Recursion and Tail Call Optimization Work
      2. Accumulators in Tail Recursion
      3. Limitations of Tail Recursion
      4. Tail Recursion Case Studies
        1. Tail Recursive Reverse String
        2. Tail Recursive Find Substring
        3. Tail Recursive Exponents
        4. Tail Recursive Odd-Even
      5. Summary
      6. Further Reading
      7. Practice Questions
    9. Chapter 9: Drawing Fractals
      1. Turtle Graphics
      2. Basic Turtle Functions
      3. The Sierpiński Triangle
      4. The Sierpiński Carpet
      5. Fractal Trees
      6. How Long Is the Coast of Great Britain? The Koch Curve and Snowflake
      7. The Hilbert Curve
      8. Summary
      9. Further Reading
      10. Practice Questions
      11. Practice Projects
  9. Part II: Projects
    1. Chapter 10: File Finder
      1. The Complete File-Search Program
      2. The Match Functions
        1. Finding the Files with an Even Number of Bytes
        2. Finding the Filenames That Contain Every Vowel
      3. The Recursive walk() Function
      4. Calling the walk() Function
      5. Useful Python Standard Library Functions for Working with Files
        1. Finding Information About the File’s Name
        2. Finding Information About the File’s Timestamps
        3. Modifying Your Files
      6. Summary
      7. Further Reading
    2. Chapter 11: Maze Generator
      1. The Complete Maze-Generator Program
      2. Setting Up the Maze Generator’s Constants
      3. Creating the Maze Data Structure
      4. Printing the Maze Data Structure
      5. Using the Recursive Backtracker Algorithm
      6. Starting the Chain of Recursive Calls
      7. Summary
      8. Further Reading
    3. Chapter 12: Sliding-Tile Solver
      1. Solving 15-Puzzles Recursively
      2. The Complete Sliding-Tile Solver Program
      3. Setting Up the Program’s Constants
      4. Representing the Sliding-Tile Puzzle as Data
        1. Displaying the Board
        2. Creating a New Board Data Structure
        3. Finding the Coordinates of the Blank Space
        4. Making a Move
        5. Undoing a Move
      5. Setting Up a New Puzzle
      6. Recursively Solving the Sliding-Tile Puzzle
        1. The solve() Function
        2. The attemptMove() Function
      7. Starting the Solver
      8. Summary
      9. Further Reading
    4. Chapter 13: Fractal Art Maker
      1. The Built-in Fractals
      2. The Fractal Art Maker Algorithm
      3. The Complete Fractal Art Maker Program
      4. Setting Up Constants and the Turtle Configuration
      5. Working with the Shape-Drawing Functions
        1. The drawFilledSquare() Function
        2. The drawTriangleOutline() Function
      6. Using the Fractal Drawing Function
        1. Setting Up the Function
        2. Using the Specifications Dictionary
        3. Applying the Specifications
      7. Creating the Example Fractals
        1. Four Corners
        2. Spiral Squares
        3. Double Spiral Squares
        4. Triangle Spiral
        5. Conway’s Game of Life Glider
        6. Sierpiński Triangle
        7. Wave
        8. Horn
        9. Snowflake
        10. Producing a Single Square or Triangle
      8. Creating Your Own Fractals
      9. Summary
      10. Further Reading
    5. Chapter 14: Droste Maker
      1. Installing the Pillow Python Library
      2. Painting Your Image
      3. The Complete Droste Maker Program
      4. Setting Up
      5. Finding the Magenta Area
      6. Resizing the Base Image
      7. Recursively Placing the Image Within the Image
      8. Summary
      9. Further Reading
  10. Index

List of Tables

  1. Table 2-1: Factorials of the First Few Integers
  2. Table 6-1: All Possible Permutations and Combinations, with and without Repetition, of the Set {A, B, C}
  3. Table 6-2: Calculating the Number of Possible Permutations and Combinations, with and without Repetition, of a Set of n Elements
  4. Table 6-3: How Power Sets Grow as New Elements (in Bold) Are Added to the Set
  5. Table 9-1: Turtle Functions in Python’s turtle Module and JavaScript’s jtg Library
  6. Table 9-2: Python-Only Turtle Functions
  7. Table 13-1: Keys in the Specification Dictionaries

List of Illustrations

  1. Figure 1-1: The Google search results for recursion link to the Google search results for recursion.
  2. Figure 1-2: I’m So Meta, Even This Acronym (I.S. M.E.T.A.) (xkcd.com/917 by Randall Munroe)
  3. Figure 1-3: The recursive centaur. Image by Joseph Parker.
  4. Figure 1-4: Sierpiński triangles are fractals (recursive shapes) that include Sierpiński triangles.
  5. Figure 1-5: Your meandering conversation stack
  6. Figure 1-6: The stack starts empty. Cards are then pushed onto and popped off the stack.
  7. Figure 1-7: The state of the call stack as the localVariables program runs
  8. Figure 1-8: A stack overflow happens when the call stack becomes too high, with too many frame objects taking up the computer’s memory.
  9. Figure 1-9: The call stack keeping track of the values in the number local variable for each function call
  10. Figure 2-1: The state of the call stack as the recursive calls to factorial() are called and then return
  11. Figure 2-2: Each number of the Fibonacci sequence is the sum of the previous two numbers.
  12. Figure 2-3: A tree diagram of the recursive function calls made starting with fibonacci(6). The redundant function calls are in gray.
  13. Figure 2-4: The stack in opStack during the exponentWithPowerRule(6, 5) function call
  14. Figure 2-5: A maze (left) along with its interior paths (center) morphed to match a biological tree’s shape (right)
  15. Figure 2-6: A filesystem is similar to a tree structure.
  16. Figure 3-1: The state of the call stack when sum([5, 2, 4, 8]) runs
  17. Figure 3-2: A [5, 2, 4, 8] array (right) is like a tree data structure (left) with only one branch at each node.
  18. Figure 3-3: The state of the call stack as the rev() function reverses the CAT string
  19. Figure 3-4: A wooden Tower of Hanoi puzzle set
  20. Figure 3-5: The series of operations for solving a four-disk Tower of Hanoi
  21. Figure 3-6: The original shape in a graphics editor (top left) and the same shape with three different areas flood-filled with a light gray color
  22. Figure 4-1: A tree (left) and three examples of non-trees
  23. Figure 4-2: A tree with root A and leaves D, G, H, and F, along with its traversal orders
  24. Figure 4-3: A linked list data structure storing HELLO. Linked lists can be considered a kind of tree data structure.
  25. Figure 4-4: The tree that stores names in our depthFirstSearch.py and depthFirstSearch.html programs
  26. Figure 4-5: The maze solved by our maze program in this chapter. Some intersections have lowercase letters that correspond to nodes in Figure 4-6.
  27. Figure 4-6: In this DAG representation of the maze, nodes represent intersections, and edges represent the north, south, east, or west path from the intersection. Some nodes have lowercase letters to correspond to intersections in Figure 4-5.
  28. Figure 5-1: A binary search repeatedly determines which half of a range contains your target item in a sorted array of items.
  29. Figure 5-2: Quicksort works by repeatedly partitioning items into two sets.
  30. Figure 5-3: The divide and merge phases of merge sort
  31. Figure 5-4: The merge step compares the two values at the start of the smaller sorted lists and moves them to the larger sorted list. Merging four cards requires only four steps.
  32. Figure 5-5: A lookup table, such as this table of products of all single-digit numbers, saves our program from repeat calculations as the computer stores the precomputed values in memory for later retrieval.
  33. Figure 5-6: The integers to multiply, x and y, are divided into halves a, b, c, and d.
  34. Figure 6-1: The set {A, B, C} within the dashed lines and some of its subsets {A, B, C}, {A, C}, and { } within the solid lines. The circles represent sets, and the letters represent elements.
  35. Figure 6-2: All six possible permutations of three wedding guests at a table
  36. Figure 6-3: A four-digit combination bicycle lock has 104, or 10,000, possible permutations with repetition (photo courtesy of Shaun Fisher, CC BY 2.0 license).
  37. Figure 6-4: Tree showing every possible k-combination (from 0 to 4) from the set {A, B, C, D}
  38. Figure 6-5: Tree showing every possible 2-combination from the set {A, B, C}
  39. Figure 7-1: A tree diagram of the recursive function calls made starting with fibonacci(6). The redundant function calls are in gray.
  40. Figure 7-2: The number of function calls sharply increases for the original fibonacci() function (top) but grows only slowly for the memoized fibonacci() function (bottom).
  41. Figure 8-1: The process of transformations that factorial(5) makes to the integer 120
  42. Figure 8-2: The process of transformations that rev('abcdef') makes to the string fedcba
  43. Figure 9-1: The spiral drawn by the program using Python’s turtle module
  44. Figure 9-2: The headings in Python’s turtle module (left) and the JavaScript jtg library (right)
  45. Figure 9-3: An equilateral triangle (left) with an upside-down triangle added to form a Sierpiński triangle, with additional triangles recursively added
  46. Figure 9-4: The three inner triangles, with midpoints shown with large dots
  47. Figure 9-5: A standard Sierpiński triangle
  48. Figure 9-6: A skewed Sierpiński triangle
  49. Figure 9-7: The Sierpiński carpet
  50. Figure 9-8: Calling turtle.begin_fill(), drawing a path, and calling turtle.end_fill() creates a filled-in shape.
  51. Figure 9-9: The Sierpiński carpet, with only the outlines of the rectangles drawn
  52. Figure 9-10: A 3D Menger sponge fractal
  53. Figure 9-11: A perfectly self-similar fractal tree generated with the left and right branches using consistent angles and lengths
  54. Figure 9-12: A more realistic tree created using random changes to branch angle and lengths
  55. Figure 9-13: The island of Great Britain, with a rough measure (left) and more precise measure (right). Measuring the coast more precisely adds 800 miles to its length.
  56. Figure 9-14: After splitting the line segment into three equal parts (left), add a bump to the middle part (right). We now have four segments of length b / 3, to which bumps can be added again (bottom).
  57. Figure 9-15: Creating three Koch curves on the three sides of an equilateral triangle to form a Koch snowflake
  58. Figure 9-16: A Koch snowflake. Some of the interior lines remain because of small rounding errors.
  59. Figure 9-17: The first three recursions of the Hilbert space-filling curve
  60. Figure 9-18: Five levels of the Hilbert curve, with line length 10
  61. Figure 9-19: Six levels of the Hilbert curve, filled in, with line length 5
  62. Figure 9-20: A box fractal, drawn to two levels
  63. Figure 9-21: The first three iterations of the Peano curve, from left to right. The bottom row includes the 3 × 3 sections that each part of the curve is split across.
  64. Figure 10-1: An example filesystem and the recursive walk() function calls over it
  65. Figure 10-2: Going from the filename to the individual attributes of a timestamp
  66. Figure 11-1: The maze as it gets “carved out” by the recursive backtracking algorithm
  67. Figure 11-2: An example maze that can be represented by a data structure
  68. Figure 12-1: Solving a numeric sliding-tile puzzle from its scrambled state (left) to its solved, ordered state (right)
  69. Figure 12-2: The task of solving a 15-puzzle can be represented as a graph with tile states as nodes and slides as edges.
  70. Figure 12-3: The 15-puzzle has undirected edges (drawn without an arrowhead) between its nodes because slides can be undone by performing the opposite slide.
  71. Figure 12-4: An example of a loop in the 15-puzzle’s graph
  72. Figure 12-5: The x, y coordinates for each space on the board (left) and the corresponding data structure index (right)
  73. Figure 12-6: If the blank space is in the bottom-right corner, down and right are the only valid slide directions.
  74. Figure 13-1: The nine example fractals that come with the Fractal Art Maker program
  75. Figure 13-2: The results of calling drawFilledSquare() (left) and drawTriangleOutline() (right) on their own
  76. Figure 13-3: The triangle produced by the first call to drawFractal() (left) and the first set of three recursive calls (right)
  77. Figure 13-4: The first level of recursive calls to drawFractal() (left) and the nine new triangles of the second level of recursive calls (right)
  78. Figure 13-5: The final Wave fractal after each triangle recursively generates three more triangles
  79. Figure 13-6: The measurements of an equilateral triangle with sides the length of size
  80. Figure 13-7: Drawing an equilateral triangle involves three forward movements and three 120-degree turns.
  81. Figure 13-8: Each step of the Four Corners example from left to right, top to bottom. Each square recursively produces four more squares at its corners, with colors alternating between white and gray.
  82. Figure 13-9: The Four Corners fractal with the first dictionary removed from the specs list
  83. Figure 13-10: In each of these four images, the turtle always moves 100 units “right” and “up” along the relative x-axis and y-axis of its initial heading.
  84. Figure 13-11: The nine fractals that come with Fractal Art Maker, with the shape-drawing functions swapped
  85. Figure 14-1: The recursive illustration on a tin of Droste’s Cacao
  86. Figure 14-2: Recursive applications of the image to the magenta pixels. If you are viewing the black-and-white image printed in this book, the magenta area is the rectangle in front of the museum visitor.
  87. Figure 14-3: The base image with a magenta area outlined in white (left) and the recursive image it produces (right)
  88. Figure 14-4: The base image with the magenta area in the monitor (top), the resized image over the base image (middle), and the final recursive image that replaces only the magenta pixels (bottom)
  89. Figure 14-5: Resizing the image to the dimensions of the magenta area can result in a different aspect ratio, causing it to look stretched or squished.

Guide

  1. Front Matter
  2. Dedication
  3. Foreword
  4. Introduction
  5. Part I: UNDERSTANDING RECURSION
  6. Chapter 1: What Is Recursion?
  7. Start Reading
  8. Chapter 2: Recursion vs. Iteration
  9. Chapter 3: Classic Recursion Algorithms
  10. Chapter 4: Backtracking and Tree Traversal Algorithms
  11. Chapter 5: Divide-and-Conquer Algorithms
  12. Chapter 6: Permutations and Combinations
  13. Chapter 7: Memoization and Dynamic Programming
  14. Chapter 8: Tail Call Optimization
  15. Chapter 9: Drawing Fractals
  16. Part II: Projects
  17. Chapter 10: File Finder
  18. Chapter 11: Maze Generator
  19. Chapter 12: Sliding-Tile Solver
  20. Chapter 13: Fractal Art Maker
  21. Chapter 14: Droste Maker
  22. Index

Pages

  1. iii
  2. iv
  3. v
  4. vi
  5. xv
  6. xvi
  7. xvii
  8. xix
  9. xx
  10. xxi
  11. xxii
  12. xxiii
  13. xxiv
  14. 1
  15. 3
  16. 4
  17. 5
  18. 6
  19. 7
  20. 8
  21. 9
  22. 10
  23. 11
  24. 12
  25. 13
  26. 14
  27. 15
  28. 16
  29. 17
  30. 18
  31. 19
  32. 21
  33. 22
  34. 23
  35. 24
  36. 25
  37. 26
  38. 27
  39. 28
  40. 29
  41. 30
  42. 31
  43. 32
  44. 33
  45. 34
  46. 35
  47. 36
  48. 37
  49. 38
  50. 39
  51. 40
  52. 41
  53. 42
  54. 43
  55. 45
  56. 46
  57. 47
  58. 48
  59. 49
  60. 50
  61. 51
  62. 52
  63. 53
  64. 54
  65. 55
  66. 56
  67. 57
  68. 58
  69. 59
  70. 60
  71. 61
  72. 62
  73. 63
  74. 64
  75. 65
  76. 66
  77. 67
  78. 68
  79. 69
  80. 71
  81. 72
  82. 73
  83. 74
  84. 75
  85. 76
  86. 77
  87. 78
  88. 79
  89. 80
  90. 81
  91. 82
  92. 83
  93. 84
  94. 85
  95. 86
  96. 87
  97. 88
  98. 89
  99. 90
  100. 91
  101. 92
  102. 93
  103. 94
  104. 95
  105. 96
  106. 97
  107. 98
  108. 99
  109. 100
  110. 101
  111. 102
  112. 103
  113. 104
  114. 105
  115. 106
  116. 107
  117. 108
  118. 109
  119. 110
  120. 111
  121. 112
  122. 113
  123. 114
  124. 115
  125. 116
  126. 117
  127. 118
  128. 119
  129. 120
  130. 121
  131. 122
  132. 123
  133. 124
  134. 125
  135. 126
  136. 127
  137. 128
  138. 129
  139. 130
  140. 131
  141. 132
  142. 133
  143. 134
  144. 135
  145. 136
  146. 137
  147. 138
  148. 139
  149. 140
  150. 141
  151. 142
  152. 143
  153. 144
  154. 145
  155. 146
  156. 147
  157. 148
  158. 149
  159. 151
  160. 152
  161. 153
  162. 154
  163. 155
  164. 156
  165. 157
  166. 158
  167. 159
  168. 160
  169. 161
  170. 163
  171. 164
  172. 165
  173. 166
  174. 167
  175. 168
  176. 169
  177. 170
  178. 171
  179. 172
  180. 173
  181. 175
  182. 176
  183. 177
  184. 178
  185. 179
  186. 180
  187. 181
  188. 182
  189. 183
  190. 184
  191. 185
  192. 186
  193. 187
  194. 188
  195. 189
  196. 190
  197. 191
  198. 192
  199. 193
  200. 194
  201. 195
  202. 196
  203. 197
  204. 198
  205. 199
  206. 201
  207. 203
  208. 204
  209. 205
  210. 206
  211. 207
  212. 208
  213. 209
  214. 210
  215. 211
  216. 212
  217. 213
  218. 214
  219. 215
  220. 216
  221. 217
  222. 218
  223. 219
  224. 220
  225. 221
  226. 222
  227. 223
  228. 224
  229. 225
  230. 226
  231. 227
  232. 228
  233. 229
  234. 231
  235. 232
  236. 233
  237. 234
  238. 235
  239. 236
  240. 237
  241. 238
  242. 239
  243. 240
  244. 241
  245. 242
  246. 243
  247. 244
  248. 245
  249. 246
  250. 247
  251. 248
  252. 249
  253. 250
  254. 251
  255. 252
  256. 253
  257. 254
  258. 255
  259. 256
  260. 257
  261. 259
  262. 260
  263. 261
  264. 262
  265. 263
  266. 264
  267. 265
  268. 266
  269. 267
  270. 268
  271. 269
  272. 270
  273. 271
  274. 272
  275. 273
  276. 274
  277. 275
  278. 276
  279. 277
  280. 278
  281. 279
  282. 280
  283. 281
  284. 282
  285. 283
  286. 284
  287. 285
  288. 286
  289. 287
  290. 288
  291. 289
  292. 290
  293. 291
  294. 292
  295. 293
  296. 294
  297. 295
  298. 296
  299. 297
  300. 298
  301. 299
  302. 300
  303. 301
  304. 302
  305. 303

The Recursive Book of Recursion

Ace the Coding Interview with Python and JavaScript

by Al Sweigart

nsp_logo_black_rk

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 [email protected] 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

About the Author

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.

About the Technical Reviewer

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.

Foreword

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, that’s something you just don’t 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 design—even when recursion is not being used. Thus, it’s 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 who’d 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: 

result = [(lambda r: lambda n: 1 if n < 2 else r(r)(n-1) + r(r)(n-2))(
          (lambda r: lambda n: 1 if n < 2 else r(r)(n-1) + r(r)(n-2)))(n)
          for n in range(37)]

Then there was the story of Chelsea, who became so effective at real-world problem-solving that she was promptly fired! Oh, you wouldn’t believe how much all the fine editors at No Starch (bless their hearts) hated these stories. “You can’t start a book by telling people stories like that. It’s 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 wouldn’t 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, I’ll have to share the true stories of Ben and Chelsea with you another time. But, getting back to the book, it’s 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 worry—this is normal! However, it’s 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

Acknowledgments

It’s misleading to have only my name on the cover. I’d 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.