From a state to a formula

Once the state is fixed, the recurrence usually falls out. It is the answer to one question: what are my choices here, and what does each leave behind?

The shape

answer(state) = combine over each choice of:
                    immediate value of the choice
                  + answer(the smaller state it leads to)

The combine is a maximum, a minimum, a sum or a boolean or, and choosing it is choosing the problem, which is the counting against optimising distinction.

Working one out

Climbing stairs, one or two steps at a time, counting the ways.

State: ways[n] is the number of ways to reach step n.

Choices arriving at n: from n-1 with a single step, or from n-2 with a double.

ways[n] = ways[n-1] + ways[n-2]

Sum, because the two groups of routes are disjoint and together they are all of them. Change the question to "fewest moves" and the sum becomes a minimum and the formula changes with it.

Forwards or backwards

The same recurrence can be written pulling or pushing:

pull:  ways[n]   = ways[n-1] + ways[n-2]      where did I come from
push:  ways[n+1] += ways[n]                   where can I go
       ways[n+2] += ways[n]

Both correct. The pull form is usually easier to reason about because each cell is written exactly once, so you can look at one line and know the cell is finished. The push form is sometimes more natural when the set of reachable next states is easier to enumerate than the set of predecessors.

Checking it before coding

Three checks catch most mistakes:

Does every choice actually shrink the state? If some branch leaves the state unchanged, the recursion does not terminate. The unbounded knapsack staying on the same item is fine only because the capacity decreases.

Does the take branch forbid what it should? In the no two adjacent problem, adding best[i-1] quietly permits the thing the rule forbids.

Is every case covered? A recurrence with a condition needs an else. The matching and non matching cases in the longest common subsequence are both required, and missing one gives a table of zeroes in half the cells.

Hand run it

Take the smallest non trivial input and compute three or four cells by hand against the formula. It takes two minutes and catches an off by one before it becomes a debugging session over a table of numbers that all look plausible.