Fibonacci Sequence in Python

The Fibonacci sequence is the most beloved number pattern in math and computer science. Start with 0 and 1, then keep adding the last two numbers together. That single rule produces an infinite list that shows up in sunflower spirals, stock charts, and whiteboard interviews: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

Why do programmers love it? It's the perfect teaching tool - small enough for a beginner to write in three lines, rich enough to teach recursion, iteration, memoization, dynamic programming, and complexity analysis all at once. Master python fibonacci and you've absorbed a huge chunk of algorithmic thinking.

Fun fact: the ratio between consecutive Fibonacci numbers converges to the golden ratio (phi approx 1.618). Nature really likes this number.

How It Works (The Intuition)

Imagine climbing a staircase, taking either one or two steps at a time. How many ways can you reach the top of an n-step staircase? The n-th Fibonacci number. Your last move was either a single step (you were at n-1) or a double (you were at n-2), and the total paths is the sum. That's the Fibonacci recurrence as a puzzle.

Formally: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Every fibonacci python solution is a different way to compute that efficiently.

The Three Approaches Compared

1. Naive Recursion - Beautiful but Wasteful

The recursive version reads like the math definition translated word for word:

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

Elegant, but here's the catch. To compute fib(5), Python computes fib(4) and fib(3). To compute fib(4), it computes fib(3) again and fib(2). By the time you reach fib(30), the function has been called over a million times. The call tree branches like crazy, and runtime grows like O(phi^n) - essentially exponential. Try fib(40) and go make a coffee.

2. Iteration - Fast, Boring, Production-Ready

The iterative approach trades elegance for raw speed. We keep two variables that hold the last two Fibonacci numbers and slide them forward:

a, b = 0, 1
for _ in range(n):
    a, b = b, a + b

No recursion, no call stack, no repeated work. One pass, one answer. This is what you'd actually ship.

3. Memoized Recursion - The Best of Both Worlds

Memoization keeps the recursive shape but adds a notebook. Every new Fibonacci number gets written into a dictionary. Ask for it again? We just look it up.

In idiomatic Python you don't even write the cache yourself - functools.cache (Python 3.9+) or functools.lru_cache does it in one decorator:

from functools import cache

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

Same naive code, but now it runs in linear time. This is fibonacci dynamic programming in its purest form.

Complexity Analysis

The takeaway: never use plain recursion for Fibonacci in real code. The exponential blowup isn't theoretical - it's a wall you hit at small n.

Common Pitfalls

Real-World Uses

Fibonacci isn't just an interview puzzle:

When to Use Which Method

Frequently Asked Questions

Why is recursive Fibonacci so slow?

Because it recomputes the same subproblems over and over. The call tree has roughly phi^n leaves, mostly duplicates. Memoization fixes this by remembering each result the first time.

What's the largest Fibonacci number Python can compute?

As large as your memory allows. Python integers have arbitrary precision - no 64-bit overflow like in C. People routinely compute fib(100000) and beyond. Use iteration or fast doubling past a few thousand.

Can I just use `functools.lru_cache`?

Yes. @lru_cache(maxsize=None) or @cache (Python 3.9+) gives you fibonacci memoization in one line. Just remember the cache persists for the function's lifetime.

Is there a closed-form formula for Fibonacci?

Yes - Binet's formula: F(n) = (phi^n - psi^n) / sqrt{5}, where phi = (1+sqrt{5})/2 and psi = (1-sqrt{5})/2. Exact in pure math, but in floating-point Python it loses accuracy around n = 70 due to rounding. Beautiful for theory, unreliable for big computations.

What's the connection to the golden ratio?

The ratio F(n+1) / F(n) converges to phi approx 1.6180339887 as n grows. Fibonacci and the golden ratio are two views of the same mathematical object - one discrete, one continuous.

Should I learn Fibonacci for coding interviews?

Absolutely. It's the canonical introduction to dynamic programming. Interviewers use it to test whether you can spot overlapping subproblems and turn an exponential solution into a linear one. Master all three versions and you're ready for harder DP problems like climbing stairs, coin change, and longest common subsequence.