CodeLudo 🔥 Daily Guides

Find the Wasted Calls: the Skill Behind Every Memoisation

✓ numbers produced by the code on this page · Published 2026-08-20

Memoisation is one of the easiest ideas in programming to explain: remember an answer instead of working it out twice. Almost every explanation shows the slow version, then the fast version, and the reader agrees — and then cannot apply it to a problem of their own.

The reason is that the explanation skips the only hard part. Knowing what to do about a repeated subproblem is trivial. Noticing that a subproblem repeats is not, because in a recursion tree the repeats are not labelled. They look exactly like the work that has to happen.

That is a perceptual skill, and perceptual skills are trained by doing them.

Find them yourself

Every call below computes some fib(k). The first time a value appears, that is real work. Every later appearance is recomputing something another branch already finished. Click the repeats.

Spot the wasted work the repeats are not labelled

Written the obvious way, fib(n) calls itself twice and each of those calls itself twice again. For fib(6) that is 25 calls in total — to compute only 7 distinct values, 0 through 6. The other 18 calls recompute something another branch has already worked out.

The waste is not spread evenly, and the pattern is worth seeing: fib(6) is computed 1 time, fib(5) is computed 1 time, fib(4) is computed 2 times, fib(3) is computed 3 times, fib(2) is computed 5 times, fib(1) is computed 8 times, fib(0) is computed 5 times. Those counts are Fibonacci numbers themselves for every value down to 1 — the recursion's own shape showing up in how often it repeats itself.

Remembering each answer the first time removes all of it. At fib(30) plain recursion makes 2,692,537 calls; the same function that checks a table first makes 59.

Wrong clicks are counted, so clicking everything does not work. Use Bigger tree once you have the eye for it.

Clicking a repeat marks the call and tells you something stronger: everything underneath it is wasted too. A repeated call does not just cost one call, it costs its entire subtree — which is where the explosion comes from.

The waste, counted

python 
def fib_calls(n, counter):
    """Plain recursion. Every call recomputes both subproblems from scratch."""
    counter[0] += 1
    if n < 2:
        return n
    return fib_calls(n - 1, counter) + fib_calls(n - 2, counter)


def fib_memo(n, memo, counter):
    """Same recursion, except an answer already worked out is never worked out again."""
    counter[0] += 1
    if n in memo:
        return memo[n]
    memo[n] = n if n < 2 else fib_memo(n - 1, memo, counter) + fib_memo(n - 2, memo, counter)
    return memo[n]


def distinct_subproblems(n):
    return n + 1 if n >= 0 else 0


print(f"{'fib(n)':>7} {'plain calls':>13} {'memoised calls':>15} {'distinct':>9} {'wasted':>13}")
for n in (6, 10, 20, 30, 35):
    plain, memo_calls = [0], [0]
    fib_calls(n, plain)
    fib_memo(n, {}, memo_calls)
    wasted = plain[0] - distinct_subproblems(n)
    print(f"{n:>7} {plain[0]:>13,} {memo_calls[0]:>15,} {distinct_subproblems(n):>9} {wasted:>13,}")

print()
print("Every value of n, and how many times plain recursion computes it, for fib(6):")
seen = {}


def trace(n):
    seen[n] = seen.get(n, 0) + 1
    if n < 2:
        return n
    return trace(n - 1) + trace(n - 2)


trace(6)
for value in sorted(seen, reverse=True):
    bar = "#" * seen[value]
    print(f"  fib({value}) computed {seen[value]:>2} time(s)  {bar}")
Output 
 fib(n)   plain calls  memoised calls  distinct        wasted
      6            25              11         7            18
     10           177              19        11           166
     20        21,891              39        21        21,870
     30     2,692,537              59        31     2,692,506
     35    29,860,703              69        36    29,860,667

Every value of n, and how many times plain recursion computes it, for fib(6):
  fib(6) computed  1 time(s)  #
  fib(5) computed  1 time(s)  #
  fib(4) computed  2 time(s)  ##
  fib(3) computed  3 time(s)  ###
  fib(2) computed  5 time(s)  #####
  fib(1) computed  8 time(s)  ########
  fib(0) computed  5 time(s)  #####

At fib(35), plain recursion makes 29,860,703 calls to compute 36 distinct values. Every one of those 29,860,667 extra calls is arithmetic that had already been done.

The distinct column is the one to watch, because it never leaves a straight line. There are only ever n + 1 different questions to answer. The exponential growth is not the problem getting harder — it is the same small set of questions being asked over and over in different branches.

The counts are Fibonacci

Look at the histogram: 1, 1, 2, 3, 5, 8. The number of times fib(k) gets computed while evaluating fib(6) is itself a Fibonacci number.

It falls out of the structure. fib(k) is reached from fib(k+1) and from fib(k+2), so its count is the sum of theirs — the Fibonacci rule, running down the tree instead of up it. The one that breaks the pattern is fib(0), computed 5 times rather than 13, because fib(1) is a base case and never recurses, so fib(0) is only ever reached from fib(2).

A reader who notices that has understood the shape of the recursion more concretely than one who has read a definition of it.

Where this generalises

Two conditions make a problem worth memoising, and the first is the one you now have practice spotting:

Both hold for Fibonacci, and for edit distance, shortest paths, knapsack, and most of what gets called dynamic programming. When only the second holds — as in merge sort, where the two halves are never the same problem twice — divide and conquer is the right shape and memoisation buys nothing.

The direction is also a choice rather than a rule. Memoising works downward from the question you were asked and computes only what it needs. A bottom-up table works upward from the base cases and computes everything, which is often faster in practice because it has no recursion and no hashing — and occasionally much worse, because it computes subproblems the answer never needed.

What this page simplifies