Recursion — classic problems

Walk through the recursion problems every competitive programmer should be able to write from memory — factorial, fast power, fibonacci (with memo), array reversal, subset and permutation generation, Tower of Hanoi, and a sketch of N-Queens.

1. Factorial and fast power

Factorial — linear recursion, the canonical first example:

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

Why care: illustrates base + recursive case and matches the mathematical definition.

Power — a^n in O(n) (naïve):

long long powN(long long a, int n) {
    if (n == 0) return 1;
    return a * powN(a, n - 1);
}

Power — a^n in O(log n) (binary exponentiation, fast power):

Key idea: a^n = (a^(n/2))² if n is even, else a · a^(n-1).

long long fastPow(long long a, long long n, long long mod) {
    if (n == 0) return 1 % mod;
    long long h = fastPow(a, n / 2, mod);
    long long sq = h * h % mod;
    return (n % 2 == 0) ? sq : sq * a % mod;
}

Contest usage: fast power is everywhere — modular inverses (Fermat), matrix exponentiation, polynomial evaluation. Memorise this one.

2. Fibonacci — and the memoization upgrade

Naïve:

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

This is O(2ⁿ) — fine for n ≤ 30, hopeless for n = 60.

With memoization (top-down DP) — O(n):

long long memo[1000005];
bool seen[1000005];

long long fib(int n) {
    if (n < 2) return n;
    if (seen[n]) return memo[n];        // already computed
    seen[n] = true;
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Every fib(k) is computed at most once. The recursion tree collapses from O(2ⁿ) nodes to O(n) distinct calls.

Takeaway: when a recursive function has overlapping subproblems (same arguments called multiple times), cache the answers. That's the leap from recursion to DP.

3. Reverse an array (or string)

Two pointers, recurse inward. Trust that the recursive call reverses the middle.

void reverseArr(vector<int>& a, int l, int r) {
    if (l >= r) return;                  // base: 0 or 1 element left
    swap(a[l], a[r]);
    reverseArr(a, l + 1, r - 1);          // recurse on inner range
}

Use: reverseArr(a, 0, (int)a.size() - 1);

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

The iterative version is one short loop, so in contests just call reverse(a.begin(), a.end()). The recursive version is here to illustrate the trust the call pattern on something concrete.

4. Generate all subsets of n elements

Pattern: include / exclude. At index i, either skip a[i] or pick it; recurse on i + 1.

void subsets(const vector<int>& a, int i, vector<int>& cur,
             vector<vector<int>>& out) {
    if (i == (int)a.size()) {
        out.push_back(cur);              // record one complete subset
        return;
    }
    subsets(a, i + 1, cur, out);          // exclude a[i]
    cur.push_back(a[i]);
    subsets(a, i + 1, cur, out);          // include a[i]
    cur.pop_back();                      // undo
}

Generates 2ⁿ subsets in O(2ⁿ · n) total.

The push_back / pop_back pair is the backtracking idiom — make a change, recurse, undo. Pair them like opening/closing braces; that's how you avoid bugs.

Variation — subset sum: prune branches whose running sum already exceeds the target.

int count = 0;
void subsetSum(const vector<int>& a, int i, int sum, int target) {
    if (sum == target) { count++; }       // found one (don't return — could continue)
    if (i == (int)a.size() || sum > target) return;
    subsetSum(a, i + 1, sum, target);     // exclude
    subsetSum(a, i + 1, sum + a[i], target); // include
}

5. Generate all permutations of n elements

Pattern: swap-in-place backtracking. For each remaining position i, try every candidate j ≥ i in that slot, recurse, then swap back.

void permute(vector<int>& a, int i, vector<vector<int>>& out) {
    if (i == (int)a.size()) {
        out.push_back(a);                  // record one complete permutation
        return;
    }
    for (int j = i; j < (int)a.size(); j++) {
        swap(a[i], a[j]);                 // choose: put a[j] at position i
        permute(a, i + 1, out);            // explore the rest
        swap(a[i], a[j]);                 // unchoose: restore
    }
}

Generates n! permutations in O(n! · n) total.

Alternative — STL: if you only need to iterate through permutations in lexicographic order, just use:

sort(a.begin(), a.end());
do {
    // use a as one permutation
} while (next_permutation(a.begin(), a.end()));

Use the recursive version when you need to prune the search (e.g. N-Queens), the STL version when you just need each permutation in order.

6. Tower of Hanoi

Problem. Move n disks from peg A to peg C using peg B. Rules: move one disk at a time; never place a larger disk on a smaller one.

Recursive insight. To move n disks from A to C:

Move top n - 1 disks from A to B (using C as helper).
Move the largest disk directly from A to C.
Move n - 1 disks from B to C (using A as helper).

void hanoi(int n, char from, char to, char aux) {
    if (n == 0) return;
    hanoi(n - 1, from, aux, to);                       // step 1
    cout << "Move disk " << n
         << " from " << from << " to " << to << "\n";  // step 2
    hanoi(n - 1, aux, to, from);                       // step 3
}

Call as: hanoi(n, 'A', 'C', 'B');

Time: O(2ⁿ) — the recurrence T(n) = 2·T(n-1) + 1 solves to 2ⁿ - 1 moves.

Why this problem is special: it is the cleanest example of trusting the recursion — once you accept that hanoi(n-1, ...) works, the three-line solution writes itself.

7. N-Queens (sketch)

Problem. Place n queens on an n × n board so that no two attack each other.

Pattern. Place one queen per row, backtracking. For each row, try every column that is not already attacked (same column, or either diagonal).

int n;
vector<int> placed;                    // placed[r] = column of queen in row r
int solutions = 0;

bool isSafe(int row, int col) {
    for (int r = 0; r < row; r++) {
        int c = placed[r];
        if (c == col) return false;     // same column
        if (abs(c - col) == row - r) return false;  // same diagonal
    }
    return true;
}

void solve(int row) {
    if (row == n) { solutions++; return; }
    for (int col = 0; col < n; col++) {
        if (!isSafe(row, col)) continue;
        placed.push_back(col);
        solve(row + 1);
        placed.pop_back();              // undo
    }
}

Initial call: placed.clear(); solve(0);

Optimization. Maintain three boolean arrays — col[c], diag1[r + c], diag2[r - c + n] — and update them in O(1) instead of scanning previous rows. Brings practical runtime within reach for n up to ~14.

Why this matters. N-Queens is the canonical backtracking benchmark. Every "place an item without conflict" puzzle uses this exact template (Sudoku, graph colouring, knight's tour).

8. Recursive binary search

Divide-and-conquer flavour of binary search — easy to see but iterative is preferred in contests (no stack frames).

int binarySearch(const vector<int>& a, int lo, int hi, int x) {
    if (lo > hi) return -1;             // base: not found
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == x) return mid;
    if (x < a[mid]) return binarySearch(a, lo, mid - 1, x);  // left half
    return binarySearch(a, mid + 1, hi, x);                  // right half
}

Use as: binarySearch(a, 0, (int)a.size() - 1, target);

Time: O(log n). Space: O(log n) stack (vs. O(1) for iterative).

This is tail recursion — each path makes exactly one recursive call, the last action of the function. A good compiler may turn it into a loop, but don't rely on it; iterative is the contest default.