Visual walkthrough — Standard library — math, random, os, sys, datetime, time, collections, itertools, functools

Step 1 — What "Fibonacci" even is (naming every symbol)

WHAT. We define a sequence of numbers, one per "index" $n$. The index is just a counter: $n=0,1,2,3,\dots$. We write $F(n)$ to mean "the Fibonacci number sitting at position $n$". The rule:

• $F(n)$ — the value we want. Reading it: "F of n".
• $F(n-1)$ and $F(n-2)$ — the two smaller problems whose answers we must already have.
• $F(0)=0$ and $F(1)=1$ — the base cases: positions so small there is nothing left to break down. These are where the recursion stops; without them it would fall forever.

WHY this rule and not another. Fibonacci is the simplest interesting function that calls itself twice. That "twice" is the whole story — one call would just be a loop; two calls make a tree, and trees can grow exponentially. It is the perfect stage on which to watch waste appear.

PICTURE. The first few values, laid out like a ruler.

Step 2 — Turning the rule into a machine (the naive function)

WHAT. We translate the maths line-for-line into Python.

def fib(n):
    if n < 2:          # the two seeds F(0)=0, F(1)=1 fold into "return n"
        return n
    return fib(n - 1) + fib(n - 2)   # the recursive rule, verbatim

Term by term against Step 1's formula:

• if n < 2: return n — this single line is both base cases. When $n=0$ it returns $0$; when $n=1$ it returns $1$. Exactly the two seeds.
• fib(n-1) + fib(n-2) — the "+" is the same "+" in $F(n-1)+F(n-2)$. Each fib(...) is a fresh call.

WHY write it this way. It is the most honest translation: the code looks identical to the definition. That honesty is also its flaw — it obeys the rule so literally that it re-does work it has already done. We are about to see that redundancy.

PICTURE. One call splits into two children — the branching moment.

Step 3 — Growing the full call tree (watch it explode)

WHAT. We fully expand fib(5): every call, every child, down to the leaves (the base cases $F(0)$ and $F(1)$).

WHY. A picture of all the calls tells us two things at once: the total amount of work (count the nodes) and — crucially — how much of that work is repeated.

PICTURE. The complete tree for fib(5). Look for the same label appearing more than once.

Notice, in the figure:

• fib(3) appears twice (once under fib(5), once under fib(4)).
• fib(2) appears three times.
• fib(1) appears five times.

Every repeated node is an entire sub-tree recomputed from scratch. The machine has amnesia: it never remembers an answer it already found.

Step 4 — The one idea that fixes everything: remember

WHAT. A cache is a small notebook. Before computing fib(k), we glance at the notebook: "did I already solve fib(k)?" If yes, copy the answer. If no, compute it once, then write it down forever.

• $\text{cache}[k]$ — the notebook entry for input $k$.
• "already written down" — this is the hit; it costs $O(1)$, a single lookup.
• "new" — the miss; we pay the real work exactly once, then it becomes a hit forever after.

WHY this specific tool — a lookup table, not, say, a faster formula. The problem in Step 3 was not hard computation; it was repeated computation. The right cure for repetition is memory, not speed. A cache attacks the exact disease we diagnosed.

PICTURE. The notebook as a table, filling in as calls resolve.

Step 5 — The same tree, now pruned

WHAT. Re-draw fib(5)'s tree, but the first time a node is computed we keep its full sub-tree; every later appearance of that same node is a leaf — a cache hit — with no children.

WHY. This is the visual payoff. The fat, doubling tree of Step 3 collapses into a thin path plus a handful of instant lookups.

PICTURE. Solid nodes = computed once (misses). Dashed nodes = cache hits (instant, no sub-tree).

Count the solid nodes: fib(5), fib(4), fib(3), fib(2), fib(1), fib(0) — six distinct inputs, one computation each. That is the essence of $O(n)$: one unit of real work per index, and no index is ever worked twice.

Step 6 — Doing it in Python for free: @lru_cache

WHAT. functools.lru_cache is that notebook, pre-built and bolted on with one line.

from functools import lru_cache
 
@lru_cache(maxsize=None)     # the notebook; None = never forget
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Reading each piece:

• @lru_cache(...) — a decorator: it wraps fib, intercepting every call to check the notebook first.
• maxsize=None — the notebook has unlimited pages, so nothing is ever evicted (best for pure recursion like this).
• The function body is unchanged from Step 2. We did not rewrite the algorithm; we only gave it a memory.

WHY lru_cache specifically. It handles the notebook bookkeeping (store, look up, key by arguments) so you cannot get it subtly wrong. LRU = least-recently-used: if you do set a size limit, it drops the stalest entry when full — a sensible default when memory is finite.

PICTURE. The decorator sits like a gatekeeper in front of the function.

Step 7 — Edge and degenerate cases (never leave a gap)

WHAT & WHY. A picture is only trustworthy if it survives the corners. Let us test the tiny and the weird.

• $n=0$ and $n=1$ (the base cases). The tree is a single node, no branching. fib(0) → 0, fib(1) → 1. Both cached and naive versions agree; there is no waste because there is nothing to repeat. The cache changes nothing here — and that is correct.
• First call after the cache is empty. Every node is a miss; the cache is being filled. So the very first fib(5) still does $O(n)$ misses — the speed-up is not from magic on call one, but from never repeating within that same call (Step 5's hits happen inside one fib(5)).
• Calling fib(5) a second time. Now every node is a hit. The whole answer returns in a single $O(1)$ lookup.
• Negative or non-integer input. The rule $F(n-1)+F(n-2)$ never reaches $n<2$ cleanly if $n$ is, say, $2.5$ or $-3$; the recursion runs away and Python raises RecursionError. The cache does not save you — a cache remembers answers, it cannot invent a base case that isn't there. Guard your inputs.

PICTURE. The degenerate trees side by side, plus the "runaway" arrow for bad input.

The one-picture summary

Left: the naive tree doubling into a bush ($O(2^n)$). Right: the same computation with a cache — a thin spine of unique computations plus instant dashed lookups ($O(n)$). Same function, same formula; the only difference is a notebook.