Fibonacci, five ways

The textbook definition recomputes the same values over and over: fib(n − 2) is evaluated once by fib(n) and again inside fib(n − 1), and the duplication compounds. The call count is exactly 2·F(n+1) − 1, which for n = 40 is 331,160,281 calls to produce one number.

The flame graph is the same kind of picture a profiler such as JDK Mission Control draws for a hot code path: wide, repeated towers are wasted work. A cache collapses them into a staircase of 2n − 1 calls.

Memoization fixes the call count but keeps a recursion depth of n — on the JVM that ends in a StackOverflowError long before n = 100,000, while a plain loop never touches the stack. The iterative loop does n additions, but the numbers grow to about 0.69·n bits, so its real cost grows with n².

Matrix exponentiation and fast doubling need only about log₂ n big multiplications, and Java’s BigInteger switches to Karatsuba and Toom–Cook multiplication for large operands — which is how a 208,988-digit F(1,000,000) arrives in milliseconds.

Interview classics are easy to recite; I’d rather show the trade-offs measured on a real JVM. The endpoint behind this race is public and CPU-heavy, so it is treated like any production API of that kind: input limits, per-client rate limiting and a concurrency gate, so one enthusiastic visitor cannot starve everyone else.

The browser race is the fallback when the API is asleep or unreachable — and a fair comparison of two runtimes doing identical arithmetic.