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.
