Fibonacci Sequence in Python

The Fibonacci sequence is one of the most famous and magical number patterns in existence!

If you start with 0 and 1, you can just add the last two numbers together to get the next one:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

It's beautiful and shows up everywhere in nature (pinecones, sunflowers, galaxy spirals!), but in computer programming, it is the absolute perfect way to learn why algorithm efficiency matters.

Three Ways to Code It

1. The Recursive Way (Simple but Slow)

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

This looks exactly like the math definition! It's super clean and elegant. But wait... to find fib(5), it needs to calculate fib(4) and fib(3). But fib(4) also has to calculate fib(3)! It ends up doing the exact same math over and over again. It is incredibly slow for big numbers! (O(2^n) time complexity)

2. The Iterative Way (Fast and Lean)

We just use a simple for loop and keep track of the last two numbers.

This is blazing fast (O(n) time) and uses almost no extra computer memory because it just updates two variables over and over! (O(1) space).

3. Memoization (The Clever Shortcut)

What if we stick with the beautiful and elegant recursive way, but give it a memory? Whenever we calculate a number for the first time, we write it down in a dictionary (our cache). Next time we need that exact same number, we just look it up instantly!

This gives us the readability of recursion with the blazing speed of iteration! (O(n) time, O(n) space).

Have fun running the code and watching the Great Race between the three methods!