Recursion — patterns and use cases

Recognise the recurring shapes of recursive code — linear, binary, multi-branch, tail, divide-and-conquer, and backtracking — and learn when each shows up in contest problems.

1. Linear recursion (one call per level)

Shape: the function calls itself once before (or after) doing some work.

Use when: the problem reduces by one element at a time — summing, transforming, walking a list.

Time: O(n) Space: O(n) stack.

Example — sum of first n natural numbers:

long long sumN(int n) {
    if (n == 0) return 0;
    return n + sumN(n - 1);
}

Example — print numbers from 1 to n (work done after the recursive call, so order is increasing):

void printAsc(int n) {
    if (n == 0) return;
    printAsc(n - 1);     // first recurse
    cout << n << " ";    // then print
}

Swap the two lines and you get descending order — a common mini-pattern to know.

2. Binary recursion (two calls per level)

Shape: the function calls itself twice.

Use when: the problem splits into two independent subproblems — Fibonacci, tree traversals, binary trees, divide-and-conquer.

Time: O(2ⁿ) without memoization (Fibonacci-like) or O(n log n) for divide-by-half problems.

Example — naïve Fibonacci (exponential):

long long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

The two subproblems overlap heavily — fib(n-3) is computed twice, fib(n-4) three times. Memoization caches results and brings it to O(n) (see the Problems topic).

Example — binary tree traversal:

struct Node { int val; Node *l, *r; };

void inorder(Node* root) {
    if (!root) return;
    inorder(root->l);            // left subtree
    cout << root->val << " ";    // current
    inorder(root->r);            // right subtree
}

3. Multi-branch recursion (k calls per level)

Shape: the function makes multiple recursive calls in a loop — one per choice.

Use when: every position has several options to explore (permutations, subsets, graph traversal, decision trees).

Time: often O(branching ^ depth) — exponential, but pruning can help massively.

Example — generate all subsets of a[0..n-1] (include / exclude each element):

void subsets(const vector<int>& a, int i, vector<int>& cur) {
    if (i == (int)a.size()) {
        // cur is one complete subset
        for (int x : cur) cout << x << " ";
        cout << "\n";
        return;
    }
    subsets(a, i + 1, cur);                // exclude a[i]
    cur.push_back(a[i]);
    subsets(a, i + 1, cur);                // include a[i]
    cur.pop_back();                        // undo
}

This is 2 calls per level, n levels → 2ⁿ leaves. The pattern of push, recurse, pop is the heart of backtracking.

4. Tail recursion vs. head recursion

Where does the work happen relative to the recursive call?

Tail recursion — the recursive call is the last action of the function. Nothing to do after it returns.
Head recursion — work happens after the recursive call returns.

Tail example — print descending:

void printDesc(int n) {
    if (n == 0) return;
    cout << n << " ";
    printDesc(n - 1);            // last action — tail
}

Head example — print ascending:

void printAsc(int n) {
    if (n == 0) return;
    printAsc(n - 1);             // recurse first
    cout << n << " ";            // then work — head
}

Why care? Tail recursion can in principle be optimized into a simple loop (no stack growth). C++ compilers sometimes do this — but never rely on it. The practical takeaway: if depth might blow the stack, rewrite tail-recursive functions as while loops manually.

5. Divide and conquer

Shape: split the problem into a few roughly equal subproblems, solve each recursively, combine the results.

Use when: the problem can be cleanly halved (or quartered) — sorting, searching, geometry, range queries.

Recurrence: typically T(n) = a · T(n/b) + O(f(n)). By the master theorem this is often O(n log n).

Example — merge sort (the canonical D&C):

void merge(vector<int>& a, int l, int m, int r) {
    vector<int> tmp;
    int i = l, j = m + 1;
    while (i <= m && j <= r)
        tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
    while (i <= m) tmp.push_back(a[i++]);
    while (j <= r) tmp.push_back(a[j++]);
    for (int k = 0; k < (int)tmp.size(); k++) a[l + k] = tmp[k];
}

void mergeSort(vector<int>& a, int l, int r) {
    if (l >= r) return;                  // base: 0 or 1 element
    int m = (l + r) / 2;
    mergeSort(a, l, m);                  // sort left half
    mergeSort(a, m + 1, r);               // sort right half
    merge(a, l, m, r);                   // combine
}

Other contest favourites: quicksort, fast exponentiation, segment tree build, closest pair of points.

6. Backtracking — choose, explore, unchoose

Shape: at every step, try each choice, recurse, then undo the choice before trying the next.

Use when: you need to enumerate or count solutions in a search space — N-Queens, Sudoku, subsets, permutations, graph colouring, paths in a grid.

Template:

void backtrack(state) {
    if (state is a solution) {
        record / count it;
        return;
    }
    for (each choice c valid from state) {
        apply(c);
        backtrack(state with c);
        undo(c);                         // ★ the crucial step
    }
}

Example — permutations of a[0..n-1] (swap-in-place style):

void permute(vector<int>& a, int i) {
    if (i == (int)a.size()) {
        for (int x : a) cout << x << " ";
        cout << "\n";
        return;
    }
    for (int j = i; j < (int)a.size(); j++) {
        swap(a[i], a[j]);                // choose: put a[j] in position i
        permute(a, i + 1);                // explore the rest
        swap(a[i], a[j]);                // unchoose: restore
    }
}

Pruning is everything. When backtracking explodes, add early termination conditions: skip choices that can't lead to a valid answer (N-Queens column/diagonal checks; Sudoku partial-validity checks).

7. Indirect (mutual) recursion

Two or more functions call each other. Less common in contests, but useful for state-machine-style problems.

Example — parity by mutual recursion:

bool isEven(int n);
bool isOdd(int n);

bool isEven(int n) {
    if (n == 0) return true;
    return isOdd(n - 1);
}
bool isOdd(int n) {
    if (n == 0) return false;
    return isEven(n - 1);
}

Contest reality: mostly a curiosity, occasionally useful for expression-parsing problems (one function handles +/- levels, another handles *//, they call each other).

Pattern cheat sheet

Pattern	Shape	Typical use	Time
Linear	1 recursive call	sum, transform, walk	O(n)
Binary	2 recursive calls	tree traversal, Fibonacci, divide & conquer	O(2ⁿ) or O(n log n)
Multi-branch	k recursive calls in a loop	subsets, permutations, search	O(k ⁿ)
Tail	recursive call is last	iterative-friendly	O(n)
Divide & conquer	k calls on n/b	sorting, geometry, ranges	O(n log n) typical
Backtracking	try / recurse / undo	enumeration, search puzzles	O(branching ^ depth), pruned
Indirect	mutual	rare; parsers, state machines	depends

In most contest problems you'll mix-and-match these — e.g. a DP solved with linear recursion + memoization, or a backtracking inside a divide-and-conquer.