Fibonacci pitfalls: branching work

The one-liner fib(n) = fib(n-1) + fib(n-2) is a famous trap: it is correct as mathematics and catastrophic as an algorithm because each call fans out into two calls that recompute the same subproblems exponentially many times. Students paste it into notebooks, wait, and conclude that “Python is slow”—the real issue is redundant work, not the interpreter.

In production data code you meet the same pattern under different names: naive dynamic-programming formulations without a table, recomputing rolling statistics inside nested loops, or evaluating the same expensive feature transform on overlapping slices. The fixes are the same family: iterate with constant memory, memoise with a dict or functools.lru_cache, or move the hot loop into a vectorised kernel.

Asymptotic growth matters more than micro-optimising a constant factor: exponential time blows up long before you need a bigger machine.

functools.lru_cache documentation: [1].