You call a recursive function. It works, but it's slow. You add more calls and it gets much slower. Something is wrong — but what?

Before we name the problem, you need to feel it. You're about to expand a recursion tree, one level at a time. Watch the call counter. See if anything looks... familiar.

Below is fib(6). At each step, predict whether the next expansion will produce a NEW subproblem or one you've already seen.

When the explosion gets painful enough, you'll get a tool to fight back. But first — experience the waste.

Not all recursion is DP. The signal is deja vu — the same subproblem appearing more than once in the recursion tree. Fibonacci has it. Subsets generation does not.

When you see repeated colors in the tree, memoization can collapse an exponential explosion into a linear scan. When every node is unique, memoization saves nothing. The question is never “does it recurse?” — it's “does the same state appear twice?”