Optimizing Fibonacci: From Recursion to Efficiency

Many times during job interviews, I was asked to write a function to calculate Fibonacci numbers. The simplest and most obvious solution is a recursive function, which looks something like this:

Let’s quickly recall the Fibonacci sequence:

At first glance, recursion seems like a natural approach. However, as you can see, the function’s growth rate is exponential (this can be proven by induction, but I’ll spare you the details). This makes recursion inefficient. Why? Because we repeatedly calculate the same values multiple times.

For example, Fn-3 is computed three times! Clearly, we can optimize this.

Let’s think about how we would calculate F20 on paper. We wouldn’t recompute values unnecessarily—we’d write them down and reuse them. Let’s implement this idea in code.

To avoid global variables you can use decorators from standart python library functools, with name lru_cache.

This is much better! However, we don’t actually need to store all previous values—just the last two numbers are enough to compute the next one.

With this final improvement, we have an efficient solution. Now, it’s time for a coffee break! ?