CSC148 Lecture Week 4

  Ah, recursion, my old enemy, we meet again. I am actually so glad that university terms are only 12 weeks long. I can only maintain good study habits for a few months at a time before I need a break, and in high school, by the last month, I was just out of gas. That was the month that we learned recursion and I just gave up, although now that I think about it, I don't think that the Waterloo Canadian Computing Competition recursion questions that my teacher gave us were suited to our skill level.

  The basic recursion we did in class with one base case and a very simple recursive statement, I can understand. Recursion is a type of algorithm where within a function, the function calls itself as a helper function. Recursion is best used on problems that can be broken down into smaller version of the same problem. One basic application of recursion is the factorial function shown to us in tutorial. For example, 6! can be broken down into 6 x 5!, which is then 6 x 5 x 4! and so on until you get to 1! which is just 1. Every factorial can eventually be broken down until 1!, so that is the base case which terminates recursion. The recursive call is then to call the function on n-1. Tracing recursion has been a good experience. I think I have a better grasp on exactly how recursion works now.