Calculating The Fibonacci Sequence

When I went to CUSEC, I actually got an interview for Direct Energy’s IS Graduate Program. The interview was surprisingly harder then the Microsoft Interview I had in the past. They asked me questions about software development, software patterns, math riddles, and programming questions.

My programming question was to output the first 10 numbers of the fibonacci sequence. A buddy of mine got the same question on his microsoft interview, so its beginning to look like a fairly common question for tech interviews. With that realization, I decided to try and program each one. Here’s my results:

Iterative Approach

def fib(n):
        first = 0
        second = 1
        for i in range(1, n):
                temp = second
                second = second + first
                first = temp
        return second

Recursive Approach

def fib(n):
        if n == 0:
                return 0
        if n == 1:
                return 1
        return fib(n-1) + fib(n-2)

Dynamic Programming Approach
I just learn this way today! Partly what inspired this post.

val = {0:0, 1:1}
 
def fib(n):
        if n not in val:
                val[n] = fib(n-1) + fib(n-2)
 
        return val[n]

So after I finished each version, I got a bit curious over how fast they were compared to each other. So I started timing each one. (I know, I know, I could just use big-O notation and figure it out easily… but what’s the fun in that?) Here’s my results:

Fibonacci(10)
Iterative: 0.0 seconds
Recursive: 0.0 seconds
Dynamic: 0.0 seconds

They’re pretty much the same. Lets push it harder.

Fibonacci(25)
Iterative: 0.0 seconds
Recursive: 0.15 seconds
Dynamic: 0.0 seconds

And harder…

Fibonacci(30)
Iterative: 0.0 seconds
Recursive: 1.63 seconds
Dynamic: 0.0 seconds

Whoa, only 5 more terms and the recursive version jumps up to 1.63 seconds? That’s some crazy exponential growth! But why does that happen? The recursive version is taken directly from the mathematical definition, which means any number it calculates, its just recalculating each number before it multiple times.

The dynamic version has recursion, but it stores each number, which saves the amount of calculation needed.  Both iterative and dynamic versions seem to be doing pretty good, so lets pit them against one another.

I tried 100, 250, 500, and they’re still the same. At around 700, the iterative version SOMETIMES is faster:

Iterative: 0.0 seconds
Dynamic: 0.01 seconds

However, at 1000, the dynamic version doesn’t work anymore:

RuntimeError: maximum recursion depth exceeded

So far, iterative is winning. I don’t like that. The iterative version just does work over and over again needlessly. So I created a loop that runs each one 1000 times, from 1 to 1000. Here’s the results:

Fibinacci(1) to Fibinacci(1000)
Iterative: 0.22 seconds
Dynamic: 0.01 seconds

Which as you can see, the dynamic version wins over time because it saves each answer. So I guess if I go on another interview, I will know which one works best.