Week 7: Recursions

Recursion is a brand new topic for me.

In CSC108, we try to use for loops and while loops. Some of recursions can be substituted by loops, however, most of them cannot.

Recursion is to define some function by calling itself inside the function body. We can do this because the process goes repeatedly for every item. From my experience so far, I think recursion is extremely useful when dealing with nested list, nested trees, and any other nested ADTs.

We first learned about nested list recursions. For the nested_depth function, without recursion, I cannot think a proper way to call the same function from the most inner list to the most outer list. I tried to write a loop for rec_max, although it can be achieved, I need to write more lines of codes and create more variable for storing things properly, which makes it not as efficient as recursion. In contrast, recursion functions are neat. In terms of what we learned, the code will usually be one line which sometimes contains list comprehension.

Also, recursion is a foundation for some ADTs such like representation of trees, linked implementations of trees and linked lists. Recursions are needed when we define a method of that class (even __init__ method can use recursion). In this case, recursion is extremely useful, since we have no idea whether this class will based on lists or tuples or sets, it may just be some abstract data type. We cannot use indexes to refer to the item we want, which makes loop almost impossible.  The examples in linked implementations of trees is extremely useful for me. It contains examples of using and not using list comprehensions, also examples of adding 1 inside or outside the list comprehension. And examples of 'max' and 'sum' help me deepen my understanding (max([])-> Error, sum([])->0) as well as tell me some tricks to avoid Error.


Also, recursion is really useful when we need to find the solution of a recursive math problem like permutations and Tower of Hanoi . 

In terms of permutation, if I want to do it without recursion, by hand, for example, it will take me a lot of time.  I will probably not be able to avoid repeated items, and probably some permutations might not be included. Recursion gives me a clear way to make sure that all the permutations will be included and none of them will repeat.

As for Tower of Hanoi, recursion did a fantastic job. It can help us to decide which cheese goes to which stool so that it is under the rule. What's more, it can tell us the most efficient way to move the cheeses, i.e. to move from one stool to another with the least steps. And we can know what exactly each move is. What makes this fantastic is that we do not need to think every step repeatedly, only a recursion relationship will solve all that for us.

In terms of how to use a recursion, I think we need to know two things: base case and recursion relationship.

When I first learn recession, I find it difficult to know what base case is. I am not used to the thinking process at the beginning. I tried to picture the whole process and end up in a mess. Now, I will first find the recursion relationship, and then think about the base case. Base case will usually be the "empty case". And I will call recursions for other cases. As for tracing recursions, I need to go from the most inner to the most outside, and use the result I have got earlier instead of further tracing it.

In conclusion, recursion is a really usefully technic for recursive things and I believe it is a foundation for what we will learn in the future of this class. I will go through the examples in  linked implementations of trees several more times to ensure I can fully understand it.