Fibonacci

Everyone who has read the book or seen the film Da Vinci Code has heard about the Fibonacci sequence. The sequence looks a bit like this:

1,1,2,3,4,7,11,\ldots

In recent years a zero has been added to the front of the sequence, and it it this sequence I will be programming. The Fibinacci sequence can be defined as:

\begin{aligned}
fibonacci_{0}{}&=0 \\
fibonacci_{1}&=1 \\
fibonacci_{n}&=fibonacci_{n-1} + fibonacci_{n-2}
\end{aligned}

I shall be using recursion to create the function which I outlined in my factorial function. This will create a small problem but I will explain how I am going to fix it.

The program is simple enough:

def fibonacci(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

It’s easy to see that I have both base cases from the definitions n==0 and n==1 and the recursive case. This program returns the n^th Fibonacci number. For example:

>>> fibonacci(10)
55

The program runs pretty quickly but the higher the number the longer it will need to run as it will need to do more recursions. If we unravel the fibonacci(5) we get:

I can easily be seen that several of the numbers are calculated more than once. Is there a better way? The answer is yes we can use a dynamic programming technique called Memoization, which basically means we cache a value the first time it is encountered and then reuse it when it is needed again. The code with memoization is:

fibcache = {}
def fibonacci(n):
    if n in fibcache:
        return fibcache[n]
    
    if n == 0:
        value = 0
    elif n == 1:
        value = 1
    elif n>1:
        value = fibonacci(n-1) + fibonacci(n-2)
        
    fibcache[n] = value
    return value

The function above checks if the value has been cached before any calculation and returns it. If it is not present, it is calculated and cached for later use. This is just one of the many dynamic programming techniques. Running the above code

>>> fibonacci(6)
8

Although this is great it would be much better to return a set of all the numbers up to a given value, this is simpe. We simply create a new function which simply adds the result of the function to a set up to the value required. The function is simply:

def printFib(n):
    l = []
    for x in range(0,n+1):
        l.append(fibonacci(x))
    return l

Note that the for loop uses a range 0-n+1 this is because the for loop in python does not include the number itself but terminates at n-1. The result of running this code is:

>>> printFib
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]