Recursion — tips, tricks, and common mistakes

The contest-tested habits that make recursive code work the first time — base-case discipline, memoization, stack-depth awareness, debugging tactics, and the bugs that catch beginners over and over.

Tips and tricks

1. Write the base case first.

Before writing any recursive logic, write the line that handles the smallest input. It is the only thing that can stop the recursion — get it right first.

int solve(int n) {
    if (n == 0) return 1;        // ← write this line FIRST
    return /* ... */;
}

2. Trust the recursion.

When writing the recursive case, assume the recursive call already works on the smaller input. Don't trace it in your head. Combine its answer with one step of work.

3. Pass big data by reference, not value.

Every recursive call gets its own copy of value parameters. Passing a 10⁵-element vector by value 10⁵ times is catastrophic.

void bad(vector<int> a, int i)     { /* copies every call */ }
void good(const vector<int>& a, int i) { /* O(1) parameter */ }

4. Memoize when subproblems repeat.

If the same recursive arguments are computed more than once, cache the result. This turns exponential into polynomial.

unordered_map<int, long long> memo;
long long f(int n) {
    if (n < 2) return n;
    auto it = memo.find(n);
    if (it != memo.end()) return it->second;
    return memo[n] = f(n - 1) + f(n - 2);
}

If the state is (i, j) with bounded ranges, prefer a 2D array over an unordered_map for speed.

5. Use global / reference variables for output collection.

Returning a vector<vector<int>> from a recursive call copies it every time. Pass an output container by reference and push_back into it.

void solve(..., vector<vector<int>>& out) { ... out.push_back(...); }

6. Pair every push_back with its pop_back.

In backtracking, make this a habit: write the pop_back immediately after writing the push_back, before writing the recursive call between them. You will never forget to undo.

cur.push_back(x);
/* recurse here */
cur.pop_back();   // ← write together as a unit

7. Prune early in backtracking.

A backtracking search with no pruning explores everything. Add invalid-branch checks at the top of the recursive call so dead branches are abandoned ASAP — a small if can speed up the search by orders of magnitude.

8. Increase the stack limit if you must recurse deeply.

On Codeforces and many other judges, you can sometimes set a larger stack for main indirectly, but the safest path is to rewrite as iteration with an explicit stack<>.

// Iterative DFS with explicit stack — no recursion at all
stack<int> st;
st.push(start);
while (!st.empty()) {
    int u = st.top(); st.pop();
    /* ... */
}

Common mistakes (and how to catch them)

Bug 1 — missing or wrong base case.

int f(int n) {
    return n * f(n - 1);     // ← no base case → infinite recursion
}

Symptom: stack overflow, segmentation fault. Fix: add if (n == 0) return 1; (or the appropriate base).

Bug 2 — recursion does not approach the base case.

int f(int n) {
    if (n == 0) return 1;
    return f(n);             // ← same argument, never terminates
}

Symptom: infinite recursion. Fix: always reduce the argument.

Bug 3 — off-by-one in the recursive argument.

long long fact(int n) {
    if (n == 0) return 1;
    return n * fact(n);      // ← should be fact(n - 1)
}

Symptom: stack overflow. Fix: read every recursive call carefully — does it move toward the base?

Bug 4 — forgetting to undo in backtracking.

void backtrack(...) {
    cur.push_back(x);
    backtrack(...);
    // ← forgot cur.pop_back(); — state leaks across branches
}

Symptom: wrong output (duplicate or contaminated entries). Fix: pair push with pop. Always.

Bug 5 — exponential blow-up from missing memoization.

Naïve fib(50) is essentially uncomputable. If you see TLE on what should be a DP problem, ask: are arguments repeating? If yes, add a memo.

Bug 6 — using int where long long is needed.

int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n - 1);  // ← overflows int at n = 13
}

Symptom: wrong answer for large n. Fix: use long long for the return type and any multiplications.

Bug 7 — global state not reset between test cases.

If your solution uses a global memo[] or visited[] and the problem has multiple test cases, clear it at the start of each test. Otherwise stale data from the previous test poisons the next.

int T; cin >> T;
while (T--) {
    memset(memo, -1, sizeof memo);  // reset before each test
    /* solve */
}

Bug 8 — stack overflow on deep recursion.

A recursion depth of 10⁶ on a 1 MB stack will likely crash. Fix: convert to iterative (explicit stack<>), or split the work, or check the judge's stack limit.

Debugging recursion

Print the call. Add a single cerr line at the top of the function showing the arguments — and an indentation level if helpful.

void solve(int depth, /* args */) {
    cerr << string(depth, ' ') << "solve(" << /*args*/ << ")\n";
    /* ... */
}

The indented trace shows exactly which branches are explored.

Test the base case alone. Run the function with the smallest input first — solve(0), solve(empty array). If that's wrong, nothing else can be right.

Test one level above the base. solve(1) should produce one recursive call to solve(0) and combine its result. If solve(1) is wrong but solve(0) is right, the bug is in the combining step.

Reduce the input. When a recursive solution gives the wrong answer for n = 100, try n = 3 or n = 4. Recursion bugs almost always show up on tiny inputs and are far easier to trace there.

Assert your invariants. If you assume l <= r in a recursive function, write assert(l <= r); at the top. The first crash localises the bug.

From recursion to DP — the most useful upgrade

Many DP solutions are easiest to think of as recursion + memoization. Here is the recipe:

Write the recursion for the problem, ignoring efficiency.
Identify the state — what arguments uniquely determine the answer? (Usually one or two ints.)
Detect overlap — does the recursion call itself with the same arguments multiple times? If yes…
Add a memo — array (if state is bounded ints) or map (if more complex).
(Optional) Convert to iterative bottom-up if you need extra speed or to avoid stack depth.

Example — unbounded knapsack:

int memo[1005][1005];   // states (i, capacity)

int solve(const vector<int>& w, const vector<int>& v, int i, int cap) {
    if (i == (int)w.size() || cap == 0) return 0;
    int& res = memo[i][cap];
    if (res != -1) return res;
    int skip = solve(w, v, i + 1, cap);
    int take = (w[i] <= cap) ? v[i] + solve(w, v, i, cap - w[i]) : 0;
    return res = max(skip, take);
}

The recursive call structure exactly mirrors the DP recurrence. Most contestants find this style easier to write correctly than bottom-up DP, especially for problems with non-obvious state transitions.

Final checklist before submitting

Before you hit submit on a recursive solution, run this checklist:

Base case is correct and matches the smallest valid input.
Recursive call moves toward the base case (smaller argument).
Big inputs passed by reference, not by value.
Backtracking changes are undone (every push has a pop).
Memoization added if the same subproblem appears multiple times.
long long used where overflow is possible.
Globals cleared between test cases.
Recursion depth is safe for the given constraints.

Most recursion bugs are caught by one of these eight checks.