All the fibonacci sequence algorithms you will ever need
This blog post shall given an overview over different methods to compute the fibonacci sequence or parts of it. Since this is a common interview question, you may print out this blog article and show it to your potential employers, not only to demonstrate how specialized your abilities are in the broad area of fibonacci computation but also to demonstrate your humor and free spirit.
TL;DR: Type "fast fibonacci algorithm" into your mobile browser before the eyes of your soon-to-be boss and download the resulting algorithm.
The silly algorithm
O(wtf this is calling itself twice recursively must be something truly horrific)
def fib(n): if n < 2: return n else: return fib(n-1) + fib(n-2)
The naive algorithm
Simply generate the entire fibonacci sequence, discarding unneeded values.
# Utilities def seek(n, seq): it = iter(seq) for _ in range(n): next(seq) return it def at(n, seq): seek(n, seq) return next(seq) # Implementation def fib_sequence(): a = 0 b = 1 while True: yield a yield b a += b b += a def fib(n): return at(n, fib_sequence())
Search the internet for "fast fibonacci algorithm", find this page https://www.nayuki.io/page/fast-fibonacci-algorithms, and download the source code for fast doubling from that page. This is the only fibonacci implementation you will ever need. Use this and see how amazed (or potentially angry or scared) recruiters will be at how fast you can compute any fibonacci number.
Bonus: Recursive naive
This is like the naive algorithm generating the entire sequence except that it's recursive, much more pretty and it will fail after a couple hundred iterations because the python joksters have out of pure trolling prowess not yet implemented proper tail call optimization
def fib_sequence(a=0, b=1): yield a yield from fib_sequence(b, a+b) ...