What is Recursion

It’s the seventh week of CSC148 and I took the midterm for CSC148 as well as CSC240 and I don't have much time to sit down and think about what is recursion, but since I’ve survived the week, I finally had some time to write down my thoughts on recursion.

Recursion, in my own viewpoint, is to divide a problem into several smaller problems which are easier to solve and the solutions of these smaller problems, when combined together, formed the complete solution to the original problem. Here I take a quite simple example: the Fibonacci sequence (see http://siyangcsc148w3.blogspot.ca/2014/01/some-thoughts-on-recursion.html for detail). Suppose we want to know the nth element in the sequence, then we need to know the (n-1)th and (n-2)th element in the sequence since all elements in the Fibonacci sequence is the sum of two elements that are immediately precede it and to know the two elements, same process will be applied until we reach the first two elements which are defined to both be 1. So the process is actually breaking bigger problems down to smaller problems until a solution is reached and then the solution is passed back and combined to form the complete solution. Here the solution to the smallest problem is called the base case and the process of reaching complete solution is called recursive steps or constructor cases.

But then comes the question: why should we use recursion? I’ll say that the use of recursion could significantly reduce the length and complexity of the program when used properly. (Check my previous post http://siyangcsc148w3.blogspot.ca/2014/01/some-thoughts-on-recursion.html for detail). Like the function we use in assignment1 for moving cheeses among four stools. A recursively defined process only requires 3 lines to reach the goal while it would be quite lengthy to write a procedural function since there are so many cases that one could easily miss something and even one does consider all cases, the code could be quite lengthy and became harder to understand than the 3-line recursive function. However when can we say is a good time for recursion? Certainly, many recursion could be written in for loops like the problem 1 in the extra section of lab 4 – write a recursion function that reverses string s and it could be easily written in for loops as we learned in CSC108, and it only requires 3 lines. So reverse a string might not be a good time for us to use recursion since recursion neither reduces the length of the code nor makes it easier to understand. Nevertheless, there is someplace that recursion could play an important role – when a program requires consideration of many different cases in for loops, recursion could be quite useful as the assignment1 I mentioned earlier. So, when thinking about using recursion, first consider the for-loop version of the program, and if the for-loop version doesn’t require considering too many cases and is not hard to understand, then use for loops instead of recursion. Also, if we want different solutions from the same problem, then recursion is, I’ll say, useless since recursion is based on the assumption that smaller problem only has one unique solution which can be used to construct the solution for bigger problems. One more thing, recursion couldn’t be used on particularly large problems since most programming languages limit the recursion depth to a certain level to avoid crashing of the whole system so when encountering particularly large problems, either use specially designed recursion or find another way without recursion.

In the end, I want to discuss a bit about debugging recursion. Basically a recursion needs a base case and recursive steps that lead to the base case or at least, smaller cases. You can find more on my previous slog http://siyangcsc148w3.blogspot.ca/2014/02/at-end-of-this-slog-httptracycsc148.html.