Week 4: Recursion

This week was all about the return of recursion. I honestly don't mind recursion. It's just another way to solve different types of problems. When I'm working on problems involving recursion, I like to try to trace the entire sequence in my head or on paper (well at least the beginning of the sequence) before I even start the problem. Occasionally, for complex situations, the recursion is hard to follow but I find that, most of the time, a simple (almost trivial) solution exists.

However, when we were working on the first exercise involving the Fibonacci sequence (where we had to determine what the sum of all Fib numbers from F(0) to F(n) was), I'll admit that I really did not see the solution. In my scratch work, I just tried to make a list of the sums from 0 to n for a few small values of n (ie. the sum for n = 1 is F(0) + F(1) = 0 + 1 = 1). That did not seem to lead me anywhere. Even after Prof. Heap drew up a table to record the values on the tablet, I really could not see any type of relation between F(n) and the sum of F(n) from 0 to n. When the relationship was finally revealed (where the sum of F(n) from 0 to n equals F(n+2) - 1), I felt like slapping my forehead because I was looking for a complicated solution where there was none. Sometimes, it hurts to overthink things.

Assignment 1 was due last Monday and I don't think I did too badly on it. The first question involving the sum of the angles in a polygon of n vertices was pretty straight forward. Divide a polygon of n+1 vertices into a triangle and a polygon of n vertices and apply the induction hypothesis. That took all of 5 minutes. Questions 2 and 3 took me a bit more time though. Especially trying to determine some type of recursive structure for the menus in question 2. Once again, I was overthinking the problem and the simple answer just passed me by. Hopefully I'll be able to kick the habit before the test. Question 3 didn't take as long. What confused me in the beginning was how to apply the principle of well-ordering to a question that involved no sets. I actually determined the answer to this question while lying awake in my bed early Saturday morning. It was one of those "Eureka!" moments. I'm hoping I'll be able to conjure up another one of those moments if I get stuck on the midterm next week.