This week we covered chapters 9, 10, and 11 of A Common-Sense Guide to Data Structures and Algorithms, 2nd ed. by Jay Wengrow (link). I’ve been coding along in Python on my Github.
The topics discussed:
- Stacks
- Queues
- Recursion
Crafting Elegant Code with Stacks and Queues
- “In fact, a stack doesn’t even care about what data structure is under the hood. All it cares about is that there’s a list of data elements that act in a LIFO way.”
- These are concepts you encounter in real life — stacks of plates, queues in lines, rotating stock in a grocery store.
- Dennis uses queue concepts (FIFO) more often than stacks.
- Jameson said stashes in Git are another example of using stacks.
Recursively Recurse with Recursion
- Jameson had encountered this in his career, but didn’t know what it was called.
- We talked about when you’d use recursion in actual problems — traversing a hierarchical file structure, solving a Sudoku, solving a maze, and pathfinding and “damage over time” in video games.
- Recursion is another tool in the toolbox, if it makes sense to use it.
- “Now that you’ve seen how recursion works, we can use it to solve certain problems that would otherwise be uncrackable.” By definition, I guess. But you can do this without functions calling one another; you can use a stack with a function.
- How common is it to forget the base case? You’ll know pretty quickly when it crashes. Houston recommended writing the base case first so you don’t forget.
Learning to Write in Recursive
- I like how this book shows you how to think about problems recursively, even though recursion may not be the best solution. It’s about finding smaller versions of the same problem.
- The Staircase Problem is an example of a depth-first solution space traversal.
- Jamie: Recursion seems more popular in “pure functional” languages. You don’t have many (if any) loops in Rust, Haskell, and F#. (http://learnyouahaskell.com/recursion) Functional languages are more declarative than imperative (e.g., for-loops), which involve doing more recursion.
- https://two-wrongs.com/myth-of-the-day-functional-programmers-dont-use-loops
- https://blog.knoldus.com/tail-recursion-in-java-8/
- We ended up going on a tangent about category theory and functional programming languages given how recursion is more common there.