The recursion framework

A recursive function is a contract: given these arguments, it returns exactly this. Most broken recursion is not a broken recurrence. It is a function whose author could not say in one sentence what a call returns, and so wrote a body that returns a count on one branch and appends to a list on another.

Five steps fix that, in this order. Each one is answerable only once the previous is settled, which is why skipping to the body is what costs the time it appears to save.

1 · Name the decision

At each step, what single choice is being made? Not "how do I solve this" — what does one node of the recursion tree decide?

The running example: count the ways to pay an amount from a set of coin values, each value usable any number of times. Amount 4, coins [1, 2, 3].

Two candidate decisions:

• A — which coin do we add next?
• B — for coin number i, do we take one more of it, or move past it for good?

Both are legal recursions. They are not the same design, and they do not return the same number.

2 · Name the subproblems the decision creates

Decision A: choosing coin c leaves "pay 4 - c from the same coin set". One argument shrinks, the coin set does not, so there is one argument and one branch per coin.

Decision B leaves two subproblems, one per branch. Take one more coin i: "pay r - coins[i], still allowed to use coin i". Move past it: "pay r, using only coins from i + 1 onward".

A subproblem has to be the same problem on smaller input. If describing it needs a word the original problem does not contain, the decision is wrong or an argument is missing.

3 · Write the signature, then the mission statement

The mission statement is one sentence saying what a call returns, and it is written before the body:

def ways(i: int, r: int) -> int:
    """Number of distinct coin multisets drawn from coins[i:] that sum to exactly r."""

One sentence, naming every argument and the return. The word exactly is doing work: it rules out the reading where r is a budget rather than a target.

A good mission statement is one a stranger could write the body from. Being unable to write it at all usually means step 1 is not finished.

The common failure has a recognisable shape:

def helper(i, r, path, out):   # mission: ?

Two accumulators and no return value, written in the hope that the meaning will emerge from the body. For a mutating helper the mission statement is still one sentence — "appends to out one copy of every multiset from coins[i:] summing to r" — and writing it is what tells you the copy is needed. That whole family has its own rules in backtracking.

4 · Write the recurrence

Each branch of the decision becomes one term:

def ways(i, r):
    skip = ways(i + 1, r)
    take = ways(i, r - coins[i]) if r >= coins[i] else 0
    return skip + take

Now check both terms against the sentence, out loud. ways(i + 1, r) is "multisets from coins[i+1:] summing to r" — the branch that never uses coin i again. ways(i, r - coins[i]) is "multisets from coins[i:] summing to r - coins[i]" — one coin i is committed, and i stays available so a multiset can hold several of it.

The two terms are disjoint: one uses coin i at least once, the other never does. Together they cover every multiset. Disjoint and covering is the whole proof obligation for a counting recurrence, and it takes ten seconds to state. Skip it and the same answer gets reached by two paths, silently doubled.

5 · Derive the base cases

Base cases are the smallest instances of the mission statement, not exceptions to it. Read the sentence with the smallest arguments and the answer falls out:

• r == 0 — exactly one multiset sums to 0, the empty one. Return 1.
• i == len(coins) and r > 0 — nothing left to draw from, so no way to reach a positive sum. Return 0.

Deriving beats guessing. Returning 0 at r == 0 is the most common bug in this family, and it comes from treating a base case as "where we stop" instead of "the case the sentence already answers".

The five steps of writing a recursion, with the recurrence and the base cases both read off the mission statement100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

The decision is the design

Run both decisions on amount 4 with coins [1, 2, 3].

Decision A gives ways(r) = ways(r-1) + ways(r-2) + ways(r-3) with ways(0) = 1, so ways(1) = 1, ways(2) = 2, ways(3) = 4, and ways(4) = 4 + 2 + 1 = 7.

Decision B gives 4: {1,1,1,1}, {1,1,2}, {2,2}, {1,3}.

Neither is buggy. A counts ordered sequences, B counts multisets, and the gap is the orderings: {1,1,2} has 3! / 2! = 3 arrangements and {1,3} has 2, so 1 + 3 + 1 + 2 = 7. If the question asked for combinations, decision A was wrong before a line of code existed — and no amount of debugging the body finds it, because the body is a faithful implementation of the wrong step 1.

Cost differs too. Decision B has (n + 1) × (amount + 1) distinct states — 4 × 5 = 20 here — so memoising collapses the tree to at most 20 evaluations. Naming the state space is how you know what memoisation buys before writing it; the counting method is in complexity by counting.

Depth is the other cost. Python's default recursion limit is about 1,000 frames, so decision B on amount = 10⁵ with a coin of value 1 descends 10⁵ frames on one branch and dies before it is slow. When depth tracks the input size rather than the number of decisions, run the recurrence bottom-up as a loop.

In an interview

Say the five steps as you do them. "The decision is whether to use coin i again or move past it. That leaves two subproblems. So the function is ways(i, r), the number of multisets from coins[i:] summing to exactly r. The recurrence is skip plus take, and they are disjoint because one branch never uses coin i. Base cases: r == 0 is 1, running out of coins with r > 0 is 0."

That transcript is most of the grade before you type, because it demonstrates the thing being tested: that the code will be a consequence of a stated contract rather than a guess that got adjusted until the examples passed. It is step 4 of the solving loop with the precondition made explicit — the problem decomposes into instances of itself.

The mistake that loses points: writing def helper(i, path, res) and starting the body. An interviewer cannot check a body against a contract that was never stated, and neither can you, so the debugging turns into changing i + 1 to i to see what happens.

Check yourself

You keep the mission statement "multisets from coins[i:] summing to r" but write the recurrence as ways(i+1, r) + ways(i+1, r - coins[i]). What did you build?

The one-of-each version: advancing i in the take branch forbids reusing a coin. It is a correct recursion for a different question — with [1, 2, 3] and amount 4 it returns 1, only {1,3}, instead of 4. One character is the whole difference between unlimited and at-most-one.

A partner's solution returns 0 for every input. Their base case returns 0 when the remaining amount is 0. Explain the bug without running the code.

Every valid path ends at r == 0, so every leaf that represents a real payment contributes 0 and the sum of zeros is 0. Derived from the mission statement, that case returns 1: there is exactly one multiset summing to 0.

Amount 100 with coins [1, 5, 10, 25]. How many states does the take-or-move-past framing have, and what does that number tell you?

(4 + 1) × (100 + 1) = 505. Memoised, the search does at most 505 evaluations regardless of how many leaves the raw tree has, so 505 — not the tree — is the honest complexity to quote.