Week 7: Recursion

Since the beginning of this semester, recursion has become the most important concept for this course: we are talking about it at class, practicing it in lab and writing codes using it basically for everything.

But what's recursion?

By definition, "recursion is the process of repeating items in a self-similar way" (from Wikipedia). But, in my opinion, I usually just think it as another name for induction (since it works similarly with induction, and I know they are different). we construct the base case (or cases), and then define certain rule on how to construct other cases based on the base case. In my opinion, so far in this course, mostly, we use recursion for two purposes: construct a data type (such as tree) and define a method/ collect data on a recursively-defined class/ data type.

Personally, I wouldn't say recursion is hard. In my opinion, it sometimes becomes a problem is because that it is a comparatively new concept and we are still learning it. But, in fact, it is not a new concept. However, we did not learn it from CSC108. We were exposed to this concept in different mathematics classes (calculus, math concept) and CS courses which focus on computation complexity. In my opinion, induction, structural proof and recursion are essentially same. All we need to consider is that find out what's the base case (or cases) and rules to construct cases. And to solve these two questions, there are a few methods.

The first one is drawing a processing diagram. The only path that lead to the output is the simplest case. If it's not, we call recursion on it to simplify it until it reaches the base case. The diagram is very useful tool when you start working on recursion (in my opinion), since it's straightforward and simple. But, it takes time to finish the picture. The second way is better than the first one, since it's more abstract and it saves time. It's to write down the mathematical function, which is the essence of the code (sometimes the math function is same with the code). We've met an example, which appeared on the handout of A1 (for Hanoi tower).

As I mentioned above, recursion is used everywhere in this course, for example, A2. In my opinion, tree is a perfect example to demonstrate recursion, because we construct tree by recursion (base case: root node) and almost every tree method needs recursion (since tree is recursively constructed). More specifically speaking, the basic element of a tree is a node, and everything is based on the node. For example, if we are asked to define a tree method, first we need to ensure it works for the root node.

These are what I think about recursion.