Overview

You may run across combinatorial problems that seem almost impossible to solve. They may involve a strenuous amount of casework or "bashing", but usually, many such problems can be solved via recursion. Recursion models a problem in terms of smaller versions of itself. In math competitions, recursion is especially useful in path counting, constrained arrangements, and step-by-step probability processes.

Recursion?

• Recursion is using smaller solutions of a problem to solve bigger ones. For instance, if we let $f(n)$ be a solution for a problem considering $n$ parameters, we may be able to get $f(n+1)$ in terms of $f(n)$. $f(n)$ may be something like the number of certain arrangements of a sequence of orders considering the first $n$ of them, or something completely different. It depends on the problem!
• Recursion needs a state, transition rule, and a base case:

  • A state is $f(n)$, the value we're trying to compute as a function of some parameter $n$.
  • A transition rule is an equation expressing one state in terms of smaller ones. For instance, $f(n) = 3f(n-1) + f(n-2)$ is a transition rule. Using this, we can get $f(n)$ solely by using $f(n-1)$ and $f(n-2)$.
  • A base case is a small case like $f(0)$ or $f(1)$ that we can solve manually without using recursion.

Demonstration

Consider the following combinatorial problem:

How many arrangements are there of $k$ distinct values?

Clearly, this is just $k!$. However, to demonstrate recursion, we will transform this problem. Let $f(n)$ denote the number of arrangements of $n$ numbers where $1 \le n \le k$. If we know $f(k-1)$, we can also find $f(k)$. Since $f(k)$ considers one more value than $f(k-1)$, there are $k$ places to insert that new value into each of the $f(k-1)$ arrangements. Hence:

For our base case, we consider $f(1)$. Obviously, there is only one way to arrange $1$ value, so $f(1) = 1$. Writing out a couple more values using our transition, we see:

1. $f(2) = 2 \cdot f(1) = 2$
2. $f(3) = 3 \cdot f(2) = 6$
3. ...

We can see recursion also gives $f(k) = k!$, as desired.

Use Cases

Recursion is often simpler but a more tedious method than conventional combinatorial techniques. One can find a couple base cases, a transition statement, and then use recursion to iteratively find their answer as they work upwards/downwards.

Worked Example

How many ways can you climb a staircase of 5 steps if each move is 1 or 2 steps?

We will solve this using recursion. As always, we begin with a base case. For $f(1)$, there is only one step, so $f(1) = 1$. For $f(2)$, we can climb the staircase in two ways:

1. Take two steps of length $1$.
2. Take one step of length $2$.

Hence, $f(2) = 2$. Now we come up with a transition statement. Observe that for $f(k)$ where $k \ge 3$, the last move in any valid climb is either:

1. A step of length $1$, preceded by some arrangement climbing $k-1$ steps. There are $f(k-1)$ such arrangements.
2. A step of length $2$, preceded by some arrangement climbing $k-2$ steps. There are $f(k-2)$ such arrangements.

These two cases are disjoint (they differ in the final move) and cover every possibility, so:

Applying this up to $k = 5$:

1. $f(3) = f(2) + f(1) = 3$
2. $f(4) = f(3) + f(2) = 5$
3. $f(5) = f(4) + f(3) = \boxed{8}$

Dynamic Programming

Look again at the staircase example. To get $f(5)$ we used $f(4)$ and $f(3)$, but computing $f(4)$ also needed $f(3)$. If we restarted the breakdown every time we met a smaller state, the same values would get recomputed over and over, and the work would pile up fast. The fix is to write each value down once and reuse it.

This is the idea behind dynamic programming, a common technique used in competitive programming. Rather than starting at $f(5)$ and breaking it down, we start from the base cases and build upward (bottom-up), recording each result:

Every entry depends only on entries already written, so a single left-to-right pass finishes the count. On a contest this is usually all that recursion means in practice. You find the base cases, find the transition, then fill in a line of numbers until you reach the one you want.

Recursion and dynamic programming are two views of the same idea. The transition describes how states relate to each other, and dynamic programming is the bookkeeping that turns that relationship into numbers without wasted effort.

One more tool comes for free. If a state is forbidden, say a step you are not allowed to land on, set its value to $0$ and keep filling as usual. Arrangements that would have passed through it contribute nothing, and every other count stays correct.

Choosing a Good State

Writing the transition and base cases is usually the easy part. The real skill is choosing the state, meaning deciding what information $f$ should depend on. A useful state has two properties:

1. It carries everything you need to keep counting. Once you know the state, the number of ways to finish should not depend on how you got there.
2. It stays small. Fewer parameters means fewer values to track and less room for error.

In every example so far a single number was enough: the step you are on, the height of the staircase, the count of values arranged. Some problems need more.

A Two-Dimensional Example

Starting at the bottom-left corner of a $4 \times 3$ grid of unit squares, how many paths reach the top-right corner if every move goes one unit right or one unit up?

One number cannot say where you are on a grid, since a position needs two coordinates. So let $f(i, j)$ be the number of paths from the start to the point $i$ units right and $j$ units up. To arrive at $(i, j)$, the last move came either from the left, from $(i-1, j)$, or from below, from $(i, j-1)$. These cases are disjoint and cover everything, so:

The base case is the starting corner, $f(0, 0) = 1$. Every point on the bottom edge or the left edge has exactly one path, reached by walking straight along that edge, so $f(i, 0) = f(0, j) = 1$.

Filling the grid from the bottom-left upward, with rows for $j = 3$ down to $0$ and columns for $i = 0$ to $4$, gives:

The top-right entry is $\boxed{35}$. As a check, a path uses $4$ rights and $3$ ups in some order, and choosing which $3$ of the $7$ moves are ups gives $\binom{7}{3} = 35$, matching the table. Grid path questions like this one appear regularly on the AMC 8 and AMC 10!

This is the same transition as the staircase, now spread across two directions. Whenever a problem tracks a position on a grid, an amount of two separate resources, or any pair of quantities that change independently, a two-parameter state $f(i, j)$ is usually the right place to start. Don't be afraid by having multi-dimensional recursion states!

Recognizing These Problems

On the AMC, a few signals suggest recursion or dynamic programming will work:

1. The problem builds up step by step, like climbing stairs or extending a sequence one term at a time.
2. A local constraint limits how consecutive choices interact, such as no two adjacent letters being equal.
3. You are counting paths, tilings, or arrangements on a grid or a line.
4. The answer for size $n$ looks like it should depend on the answer for size $n-1$ (and maybe $n-2$).

When you notice these, define a state, ask what the last move could have been, and turn that into a transition.

Practice Problems

Problem 1. A frog can jump 1 or 2 lily pads at a time. How many different ways can it reach the 6th lily pad from the start?

Problem 2. A sequence starts with 1, 1, and each new term is the sum of the two before it. What is the 9th term?

Problem 3. How many ways can you tile a $2 \times 5$ grid using only $1 \times 2$ dominoes placed horizontally or vertically?

Problem 4. You are climbing stairs and can take 1, 2, or 3 steps at a time. How many ways can you reach step 7?

Problem 5. A bug walks on a number line starting at 0. Each second it moves $+1$ or $-1$. How many paths of length 6 return the bug to 0 at the end?

Problem 6. How many strings of length 8 made of only A and B contain no two consecutive B's?

Problem 7. On a $3 \times 3$ grid of unit squares, how many paths go from the bottom-left corner to the top-right corner using only unit moves right and up, if the lattice point $(1, 2)$ is blocked and cannot be visited?

Problem 8. A staircase has 8 steps, but step 5 is cracked and cannot be landed on. You may still pass over it with a 2-step. Climbing 1 or 2 steps at a time, how many ways can you reach step 8?