Week #7: Recursion

     Recursion was not an entirely new concept to me, as I entered into CSC148. I had dealt with smaller recursive functions on my own time and it seemed simple enough. However, as we started to write and trace more complicated examples in lecture, and began to use recursion to solve problems I never would have considered using it for before, I gained a much deeper understanding of the topic.

     A recursive function is -- at its most basic definition -- a function that calls itself. To expand on that slightly, it is a function that calls itself until it reaches a 'base case', which is the solution to the least complex version of the problem the functions solves. If there was no base case a function would hypothetically run forever, or at the very least raise an ugly error message.

     It is very important to not over-think recursion, whether you are tracing someone else's code or writing a recursive function yourself. I was very confused by the Tower of Hanoi code, initially, because I could not wrap my head around how a complex problem with many steps could be broken down to just moving a one cheese from the source to the destination. However, when I went back and read the steps I realized the code represented the steps that needed to be taken almost word for word.

     The concept of a function calling itself can seem very unsettling at first glance. We cannot use a variable name that has not been defined yet so it seems counterintuitive and circular to define a function in terms of itself. However, just like we can define x = x + 1, as long as we've already defined x to be a constant value, we can also define a function in terms of itself as long as we a have a base case.

     If we view a function as a general set of instructions rather then a unique application of these instructions recursion seems like an obvious solution. For example, while all the mail in Toronto could be delivered by a single mail carrier, who was the only one to receive instructions/training on how to do his/her job, it is much more efficient to provide many mail carriers with the same training/instructions and have them each deliver mail in a smaller subsection of Toronto.

     A recursive function does the same thing. It breaks up a function into many smaller versions of the same problem that can be solved in the same way. It then solves these smaller problems in order to solve the larger problem.

      A tree then, is not only a very useful abstract data type, it is also in many ways a physical representation of recursion. Each tree 'branches out' into many subtrees until it reaches the smallest tree possible: the leaf. Although, I have not learned much about trees yet, I look forward to applying my knowledge about recursion to our next assignment on trees, and hopefully understanding both concepts on an even deeper level.