Week 11 Revisit an Earlier SLOG Posting
This semester is going to finish and we just left only
one-week lecture. I looked back to all my postings. I realized, in retrospect,
that the recursion used in almost every single key data structure we learnt (List,
Tree, Binary Tree, etc.) Therefore, this entry I would like to revisit my slog
week 5: tracing recursion, and talk about recursion more.
l Further understanding on recursion
On my previous slogs, my
fundamental definitions and understanding about Recursion was basically
correct, but a little narrow. At that time, I only learned the tracing
recursion and recursive codes in the lists. And up to now we touched the
recursive application in many data structures, such as the Tree, Binary Tree,
LinkList and so on. Recursion is a type of mathematical thinking, which can be
flexibly used in varies kinds of problems, not just in computer science.
l Progress from then on
From the previous slog, I wrote: “the biggest
hardship I encountered was writing recursion myself. I found a stupid way to
overcome, that was, used for loop first, and then transferred it to recursion
approach.” At that time, I felt confusion and not self-confident on coding
recursion. I could only indirectly think the problem, not recursively. But this
injudicious method was limited to simple questions. What’s more, it lost the
real meaning of using recursion, which is solving problems efficiently and
conveniently. I attempt to flatten the data structure, which produced
redundancy in running time. However, due to all kinds of applications and a
number of practices on labs or assignments, I got a clearer sense on whether a
recursion should be used, and obtained stronger skills to apply recursion into
practice.
Assignment 3 this time is about this problem.
It is aimed at building our skills of coding efficiently and avoiding
repeating. In the beginning, I just flattened the entire tree into a list at
the outset and then traversed the list instead of traversing the tree. That was
because it was really easy to think and to transfer into codes. But after
forbade by professor, I tried to keep track of the game states I've seen so far
and to traverse the tree directly, which was really painful to me and I always
couldn’t get out of my inaccurate pattern. Thanks for the discussion on the
piazza and professor’s office hour, we found the way to resolve them gradually.
For instance, counting_distinct_node:
As can be seen in diagram①, the old approach I used was to
return all the nodes of the tree into a list first, and then picked the distinct
nodes from that list.
The method I improved later was to building an inner helper function
to recur the tree, and then it produced the outcome straightforward in the main
function. It is worthy to mention that I used data structure “set” instead of “list”.
Because when you add two same values in the set, it will keep only one of them,
which would be very efficient.
l Reaction to other’s slog
I really appreciate Christian Garcia’s posting, since they are quite clearly
and readable with excellent paragraph distribution and some interesting
pictures.
He also chose to revisit a slog of
recursion, same as me. He summarized lots of helpful frameworks and their
characteristics, which I agreed with. However, these frameworks will not help a
lot when we encounter the complex questions. In my opinion, we do not
necessarily dwell on the frameworks of every step. The most important thing is
to understand it, and recreate it by codes.
