This entry is in response to two previous entries (the SLOGS on Linked Lists and Recursion), and has been composed with those reflections from earlier in the course in mind. For a full list of entries, see below:
- Intro to ADT
- Abstraction and Object Oriented Programming
- Programming is Poetry for Computers
- Linked Lists & Numbers: Developing Abstraction
- Recursive Rhythms in Biology and Computing
- The Unbearable Simplicity of BSTs
- Searching for Clarity: On Search Algorithms and Communication in Computing
Looking back at my feelings towards recursion and abstract data structures earlier in this course, I have to say that I had approached this course with more bravado (borne of a confident term in CSC108) than would have been wise.
Although I understood the fundamentals of both linked lists and recursion individually, and had performed well in lab exercises, integrating the two concepts to implement depth-first search in assignment two and recursive functions in the second term test were harder for me than I’d expected. The trickiest parts for me were figuring out when to create PuzzleNodes out of Puzzles, when to start building the PuzzleNode tree, when to assign children, and how to return to a branch point to search through siblings after exhausting the search down one chain of children.
Ultimately, it was working with my group in the second assignment that really helped me overcome this hump in my coursework. My group member’s walk-through of the algorithm helped me configure my mind around the placement of the if statements, and, most importantly, to realize how to set up my base cases to effectively utilize recursion.
I realized that the goal of the depth first solver was to build a chain of PuzzleNodes doubly linked via parent and child, not to create a PuzzleNode tree – once I realized this, it was straightforward to understand the implementation: the function uses Python’s call stack as the stack, essentially performing implicit iteration; the base cases (where the if statements came into play) returned either None or a PuzzleNode; based upon the output of the function according to its base cases, recursion would either “turn back” at a fruitless leaf node (in the None case) and return to a prior branching point (i.e., the siblings would be the next items on the call stack), or add the resulting PuzzleNode to a chain. Then, it was a simple matter of following the parent attribute of the recursively generated PuzzleNodes to “walk” back up along the chain of PuzzleNodes, linking each PuzzleNode to its parent via the parent’s children attribute. It was pretty fascinating how this simple combination of a few abstract processes (tree traversal, linked list traversal, recursion) and data structures (trees, linked lists) could automate a cognitively challenging task (puzzle-solving) and complete it in a matter of seconds.
Looking back at my writing from SLOG posts #4, #5, and #7 (above), I think my conception of abstraction and recursion were much simpler than I’d realized. Moreover, alternate perspectives were incredibly helpful in figuring problems out. Now that I’ve had to apply them to a more complicated scenario, implementing the abstract ideas I had in my head were quite challenging. The transition between the processes I could visualize mentally (“walking” along linked nodes, traversing a tree with a stack, recursively generating output) and actual implementation into computer code sometimes required another set of eyes, another person’s perspective.