Wednesday 5 February 2014

Recursion and Fibonacci

This week was one of the slowest classes as it was more like a resting period to help students digest recursion. We continued recursion in lectures and Dan showed us how to break problems into smaller parts and simplify so we can solve them using recursion. We also had a lab involving recursions on which we solved some seemingly basic problems. It was a breeze to write the code with recursion otherwise we had to iterate through all the possibilities by using a variant of a for loop.  The thing with recursion is, most problems can be solved without it but using recursions is an elegant and artistic way to solve problems as it saves code and coder's time despite being ever so slightly inefficient at times.

To give an example of inefficiency on recursion let's examine finding the fibonacci sequence given the index. You would normally solve this using recursion by having a base case and then modifying our call to the method.

1
2
3
4
def fibonacci(index):
    if index <= 1:
        return 1
    return fibonacci(index-1) + fibonacci(index-2)

Although the recursive implementation above is elegant, it is not very practical nor efficient. Calculating fibonacci(index) requires calculating two smaller methods, which in turn require two additional recursive calls each, and so on until all branches reach index=1. Hence, the time required to calculate fibonacci(index) is exponential.

Another way to do it while still using recursion is by a technique called memoization in which, instead of calling each smaller fibonacci method we already calculated, we store them so we can just use the already calculated data instead of going through all the recursion again. This is easily done in python using dictionaries.

1
2
3
4
5
def fibonacci(index):
    stored = {0: 1, 1: 1}
    if not (index in stored):
        stored[index] = fibonacci(index - 1) + fibonacci(index - 2)
    return stored[index]

In our dictionary we hold the initial values and whenever we need to find a value that is not yet in our dictionary we simply calculate it and add it to our dictionary therefore eliminating the need to ever calculate a value more than once.