Week 7: More Recursion!

     In this week's slog post I'll be talking a bit more in depth of the topic of recursion. Like how I mentioned in the previous blog post, recursion is a tool that allows functions to call itself in order to solve smaller subproblems. It must contain a base case in order to make it recursive or else it would recursively call itself infinitely making the program crash. Similarly, recursion can be thought closely to how loops behave in programming. Where loops may iterate through a list or may loop itself as long as the boolean condition is true, recursion takes a similar approach of checking where a circumstance is met and then recursively call when available. If we were to use the built in sum function in Python, we are only allowed to take the sum of integers in a flat list. However with the assistance of recursion, it is possible to create a way get the sum of integers where the list of elements contains integers or even nested list of integers. Thinking back to how recursion works, if we were to have a for loop that iterates each element in the base list and check whether or not the type of element is a list, we can append all items that are not in a list (in our case integers) to a new list. However if the element is a list it will recursively call itself again but this time with the sublist element as it's argument returning us the sum of that list. Moreover because of the powerful properties of recursion, no matter how deep a list maybe, it will still function properly.

     The applications of recursion can especially be essential to data structures such as linked list and trees. In both linked list and trees, they both depend on the fundamental uses of nodes and values. A node is an element in a list that refers to another object in a list, possibly values or even to other nodes. We can visualize this concept like a chain where one node refers to another until there is no possible node that refers to anything afterwards. Furthermore with the implementations of trees we may have two or more possible values that a node refers to and so forth. This makes recursion necessary to process such data because essentially linked list and trees may have nested objects of the same type. If we were to do a tree traversal (visiting each node of a tree) recursion works because it allows us to check for each children of the node (value) and whether or not it contains anything. If it does contain a value we can print that element or append it to a list or if it is a tree object this indicates that we can further go into that node and repeat the same process.