A Seriously Slow Fibonacci Function
I recently wrote an article which was ostensibly about the Fibonacci
series but was really about optimization techniques. I wanted to follow up on
its (extremely moderate) success by going in the exact opposite direction:
by writing a Fibonacci function which is as slow as possible.
This is not as easy as it sounds: any program can trivially be made slower,
but this is boring. How can we make it slow in a fair and interesting way?
A Fairly Fast Fibonacci Function
A common example of recursion is the function to calculate the \(n\)-th Fibonacci number:
def naive_fib(n):
if n < 2:
return n
else:
return naive_fib(n-1) + naive_fib(n-2)
This follows the mathematical definition very closely but it’s performance is
terrible: roughly \(\mathcal{O}(2^n)\). This is commonly patched up with dynamic
programming. Specifically, either the memoization:
from functools import lru_cache
@lru_cache(100)
def memoized_fib(n):
if n < 2:
return n
else:
return memoized_fib(n-1) + memoized_fib(n-2)
or tabulation: