Fibonacci, memoised
Memoised Fibonacci calls itself exactly the way naive Fibonacci does, but checks a memo table first: if fib(n) has already been worked out, it reads the remembered value back instead of recursing into it again. Once a value is remembered, it is set once and never recomputed.
When it is the right choice
This is the version worth using whenever the recursive structure itself is worth keeping, for readability or because the problem does not reduce cleanly to a loop. Memoisation turns the same exponential tree into one that visits each distinct subproblem once, at the cost of the memo table's O(n) space. An iterative version using two running variables would use O(1) space instead, and is the better choice when the recursive shape is not otherwise needed.
How it works
- Call fib with the given n.
- If fib(n) is already in the memo table, hand back the remembered value immediately, without recursing further.
- Otherwise, if n is 0 or 1, hand back n itself — the same base case naive Fibonacci uses.
- Otherwise, call fib on n − 1 and on n − 2, exactly as naive Fibonacci does.
- Add the two answers together, store the sum in the memo table under n, then hand it back.
Worth noticing
- The reuses counter is the whole point: on the same n, naive Fibonacci's calls counter grows exponentially while this one's reuses counter absorbs almost all of that growth, leaving only a linear number of calls that do real work.
- The tree view draws the identical shape naive Fibonacci draws, with whole repeated subtrees replaced by a single node marked as answered from memory — the saving is visible, not just counted.
- Racing this against naive Fibonacci on the same clock is the most direct argument either page makes for memoisation: watching one finish while the other is still working says more than "exponential versus linear" ever could.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Extra space
- O(n)
- Largest input
- n = 25
The largest input is a pedagogical ceiling rather than a technical one. This algorithm makes n calls, and past n = 25 the run stops being something a person can sit and watch — long before it reaches the step limit the tool enforces.