Recurrence

A recurrence describes how the answer to one state depends on answers to smaller or earlier states.

It is the rule that gives dynamic programming its structure.

Core Idea

Before choosing memoization or tabulation, the algorithm needs a recurrence. The recurrence says what value should be computed for each state.

For example, if dp[i] is the number of ways to reach step i, then dp[i] = dp[i - 1] + dp[i - 2] when each move can climb one or two steps.

The state gives a table entry its meaning. The recurrence gives the formula for filling that entry. The base cases give starting values where the recurrence stops.

Function Contract

climb_stairs(n) expects a non-negative integer number of steps.

It returns the number of ways to reach step n when each move climbs either one or two steps. dp[i] means the number of ways to stand on step i.

Python Example

def climb_stairs(n):
    dp = [0] * (n + 1)
    dp[0] = 1
 
    for i in range(1, n + 1):
        dp[i] += dp[i - 1]
        if i >= 2:
            dp[i] += dp[i - 2]
 
    return dp[n]

The recurrence adds ways from the previous one-step and two-step positions.

Building the Recurrence

Start with a state sentence:

dp[i] means the number of ways to stand on step i.

Then ask how the last move could have happened. If the last move was one step, the previous position was i - 1. If the last move was two steps, the previous position was i - 2.

That gives:

dp[i] = dp[i - 1] + dp[i - 2]

The recurrence is not guessed. It comes from splitting the final step into complete cases.

Base Cases

A recurrence needs values it can start from. In the example, dp[0] = 1 means there is one way to stand at the bottom before taking any steps.

Base cases should match the state definition. If the state sentence changes, the base cases may need to change too.

Complexity

For climb_stairs(n), there are n + 1 table entries and each entry does constant work, so the time complexity is O(n) and the space complexity is O(n).

For other recurrences, count the number of states and multiply by the amount of work needed to compute one state.

Common Confusions

A recurrence is not the table itself. The table stores values. The recurrence defines how values are related.

The state must be clear before the recurrence can be clear. dp[i] needs a precise meaning.

Another common mistake is double-counting. If two parts of a recurrence count overlapping sets of possibilities, adding them may count the same answer twice.

When To Use It

Use recurrence thinking whenever an answer can be built from smaller answers, especially in dynamic programming, recursion, counting, and optimization problems.

If the recurrence is hard to write, return to the state definition. Most DP confusion begins with an unclear state.

The Main Point

A recurrence is the rule that computes a state from earlier states. It should come from the state meaning, not from guesswork.