week 4: Recursion

  This week we learned recursion. And I tried something else myself. Basically, recursion is a powerful weapon of applying function itself to accomplish something amazing with few lines.
  We have learned recursion in mathematics. A typical example is Fibonacci sequence, who has two basic bricks at the bottom.
  Another example, the linked list. Normally we can construct it by linking Node class together. But if we think about it recursively, we can find that it is actually two things! One is head instance, another is linked list itself.

The way we construct it by itself sounds crazy and implausible at first. However, if we think deeper, it is no more than building something with something easier which we have already built. If we traced it back, gradually, we can reduce the problem with the easiest situations.
For example, when we want to remove a item with index n, we can reduce it to a simpler case as below:

As long as we find the simplest case, we can build the whole process with recursion. In this case, remove the nth item means remove the (n-1)th item for its child list. And if n==0, it reduce to the case that we remove the first item of the list.