Coding Fibonacci Seq for Google Interviews vs Codecademy Exercises

Fibonacci is one of the most fundamental coding exercises presented to beginners. Yet it is also a great example to show why Google cares so much about optimized algorithms. The seemingly simple fib exercise can test advanced coding concepts like dynamic programming and recursion related stack overflow.

So what about Fibonacci sequence? When fibonacci sequence is introduced, it is almost always a perfect example of recursion (as seen on Codecademy and Khan Academy).

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

Look at this elegant simple Python code. Go ahead and run it in your terminal, I will wait. fibonacci(3), fibonacci(5), fibonacci(25), still fast. fibonacci(500)? No error, but the execution does not finish, your terminal is now frozen.

What about fibonacci(1000)?

RuntimeError: maximum recursion depth exceeded

Turns out recursion is quite expensive in the real world. You can get StackOverflow easily and it can be hard to read and debug. Python detected that your program is problematic, and pretty much refused to run it.

If you come from a beginner background like me, chances are you were not taught to optimize this code to do memoization. Here comes dynamic programming! Fancy words that means rather than letting the system track the recursion, we are going to solve the Fibonacci…