Week 5

As Recursion week continues, some of the topics we covered were binary representation, structured lists, recursive functions, tracing recursive functions, writing recursive functions, recursive insight and recursion levels. We first jumped into Binary Representations and how to calculate them.  Using the recursive functions learned last week, we implemented the function in our lab section. The code contained parts where it recalled return values of previous values in order to return the binary representation of the desired number. We could clearly see how the design of recursion is to solve sub problems first and the tackle larger problems.

An interesting part of this week was in lecture where we played a number guessing game, and were informed whether the guess was correct or the number guessed was too high or too low. Where my reaction for a number guessing game would be to guess the first number that pops up in my mind, the path to guessing in lecture was very different. We first split the range of numbers in half thus eliminating half the list.  We then proceeded to continuously cut the list of numbers in half when told if the guess was too high or too low. At the end of the game, the exercise showed how we could calculate the cumber in less than [lg n] steps, for any number n. This same method can be applied to find the midpoint of an item in a sorted list as we eliminate half the list based on the midpoint. We then delved into O(lg n) functions which I am honestly very confused about. My goal for this weekend is to devote time to 148 and catch up with all the material and report next week with all things we cover in Week 6.