Week 7: My Summary of Recursion

As I mentioned in my recursion-tracing slog, the act of tracing recursive methods was quite simple. However, like anything else in CSC165 during the first semester and in this class, the first step to writing my own recursive function was quite difficult and I had no idea what the instructor was talking about. I sat down to really crack down on this problem. I first really read through the slides and examples that we went over in class and in the lab and tried to look for patterns. Functions are said to be recursive if they call themselves within their implementation to create repeating calls. Although the same process could be represented iteratively (i.e. with for and while loops), the instructor told us that for some problems, recursive functions are more concise and elegant, while loops can get long and complex pretty quickly.

The general pattern for more recursive functions is that they have two cases (sometimes three). The first case is known as the “base case”. This is for when even though the function might be recursive, the object might be simple enough to not require recursion. An if… expression is needed to check for that case. For a case that might be more complicated to deal with than the base case, an else… expression must be used. Ideally, this expression would reduce all the elements of the argument to the base case by iterating them through each element and calling on the same function (i.e. itself); hence, recursion. This is better explained using an example. Imagine if you want to find the number of all the elements in the list L = [1, 2, [3, 4], 5] with function element_amount(L). For a list, the base case would be a single integer element (e.g. 1) or just have the if statement check if it is not a list. It would return 1 because there is only one number. The more complex case would be invoked if the function was called on the list. Inside the else statement, we would have something like “sum([element_amount(x) for x in L])”. We’re breaking L into each element and putting them each into the element_amount function. This is with the hopes of inducing a base case for all of the elements, the sum of which will yield the number of elements in L.

To sum up, recursion is a way of finding solutions to a problem by breaking it down into smaller parts first and build up to a final solution with solutions of the smaller parts. What distinguishes this problem-solving method from the iterative way of problem-solving is that recursive functions are allowed to call themselves within their implementation. To succeed in implementing recursion, one must remember to break down the function into two cases: the first case being the base case that deals with a problem simple enough to yield a solution without requiring further recursion and the general case being the more complex case where the recursion call needs to take place. Recursion is a great way to solve problems because it makes the problem cleaner and breaks them down into more manageable means, which always leads to less headaches and working solutions!