Memoization

In yesterday's class, Danny started the lecture by showing us a simple recursive algorithm which returns the nth Fibonacci number. It turns out that this algorithm was horribly inefficient since we were repeating several unnecessary calculations. So within one minute I came up with my own code for the Fibonacci function, here it is:

def fibonacci(n):
      a, b = 0, 1
      for i in range(n):
            a, b = b, a + b
      return a   # alternatively we can return b, if we want to start with 1 instead of 0

This is much quicker than the recursive implementation, it took me about 10 seconds to get the millionth Fibonacci number, while the recursive algorithm struggled with n = 40. During the entire lecture I was waiting for Danny to reproduce this code. Instead, he suggested something called memoization which stores information from previous calculations instead of recomputing them time and time again. So essentially we would store all Fibonacci numbers in some sort of data structure and before computing another number we would firstly check that it has not already been computed to save time. In my opinion, the Fibonacci sequence is not the best example of memoization seeing as the algorithm can be written easily without the need to store things in memory (again, look at the implementation I have presented). I do, however, see the potential advantages of memoization. It is a logical approach to solving a general problem of this form, sacrifice memory space to gain computation speed. Hopefully we'll be doing some more of this in the near future.