Recursion

This is another required-topic blog post.

Recursion is a process for solving a problem. Given a large problem, using recursion means breaking down the problem into similar, smaller cases then using the same logic on those cases until a final 'base' case is reached. This base case has a simple solution. That solution is then used to solve the previous slightly larger problem and so-on until the beginning problem is solved.

Recursion is another topic I was introduced to in my second high school computer science course. In my opinion, it is one of the most confusing topics I have encountered in computer science. Solving a problem by saying, use this solution method I don't actually have yet is very counterintuitive.

Yet recursion is incredibly useful in programming. Once you can wrap your head around it, you can solve once complicated problems in just a few lines and solve others that seemed impossible. From a programming-time standpoint, recursion saves time. In the beginning stages, using recursion could take as much time as not because the logic is unfamiliar. Yet, the end result is a few lines of code whereas not using recursion could require multiple loops, variables, and if/else statements. Using recursion can save time in the creation of a program.

The other benefit is one I learned when studying the different sort methods. That is, recursion also reduces computing time. That is, after the program is written it will take a certain amount of time each it is run. Some programs have the time they take increase linearly (e.g. double for loops) as the number of variables increases. Other increase quadratically (e.g. double for loops), logarithmically, and so on. Going back to the sort methods, a quick sort, which doesn't use recursion, will take O(n^2) in the worst case. That is, it increases quadratically. Merge sort, which uses recursion, takes O(n log n) in the worst case which is a drastic improvement. While the two make take the same amount of computing time (and therefore computing power) when the numbers are small, using recursion becomes more and more beneficial from a resource standpoint as the number of times the code will be run increases.