Week 7: Recursion

Now in CSC148, recursion has been introduced to us. Essentially, recursion, at least in the context of CSC148, involves functions that call upon itself to solve a given problem. Personally, this seems useful, as there are some problems that seem recursive in nature; using recursion would be the obvious solution here. Prior to CSC148, I’ve experienced a type of “recursion” in math. In MAT137, we were taught a method of proving something called Proof by Induction. With proof by induction, we show that the base case is true. Then we assume the inductive step is true for any natural number (n) and then prove that this implies that the given statement is true for the next natural number (n+1).

At first, I was slightly confused about how exactly a function can call upon itself. It didn’t make sense to be because it seemed like we would have an infinite loop. Upon looking at more recursive functions, I realized that the Base Case is the reason for not getting an infinite loop. At one point in our function, we need to tell our function to return something. This is actually the simplest case. For example, consider the function, sum_list(x, list) whose implementation is:

return sum([sum_list(x) if isinstance(x, list) else x for x in L])

The purpose of this function is to sum up all values in a potentially nested list. The base case here is the part after the “else”. This says that if the element in list is not a list (and is therefore not a nested list), then it can only be an int or float. If that’s the case, then we simply place the value itself in the list and move on. In the case that the element is a list, we call upon sum_list again as it could be nested in many layers. However, we know that eventually we’ll reach the “base case” as there HAS to be integers within a nested list. The sum() method allows the function to return a single number from the list. Therefore, our most outer layer list is actually a regular non-nested list whose elements are just ints (or floats).

On a less academic note, I am grateful for my lab partner this week as he essentially went through recursive function with me step-by-step. I didn’t really have a solid understanding, and it was clear during the lab in which we were required to write recursive functions. The biggest problem for me was picturing all the different layers when a function called upon itself; it was difficult to keep track. However, my lab partner drew pictures involving boxes and arrows, and that allowed me to get a better grasp of recursion. To those who are struggling with recursion, I recommend two things:

1)   Continue to practice the approach taught in class. That is, go over the simplest or Base Case. This allows you to get a sense of what happens at the deepest of all layers. After working out what happens to the Base Case, work on a slightly harder situation. You’ll see that the base case comes into play here. Afterwards, work on an even harder case. You’ll see both previous situations come into play.

2)   Draw pictures. Draw boxes to indicate different layers and arrows that point to what’s happening, depending on what the recursive function is doing.