Recursion and backtracking

A recursive function solves a problem by trusting a smaller copy of itself. Backtracking takes that one step further: it walks a tree of decisions, building a candidate one choice at a time and undoing each choice on the way back up. Most "generate all …" and "count all …" problems are this one pattern, with two refinements — pruning branches that can't succeed and skipping branches that would repeat earlier output.

1. Trust the smaller problem

Every recursive function needs three things:

• a base case that answers directly,
• progress: each recursive call is on a strictly smaller problem,
• a way to combine the smaller answer into the answer.

Don't trace the whole recursion in your head. Assume the call on the smaller problem is correct — that's the induction hypothesis — and check only that one level combines it correctly.

#include <print>
#include <span>

// Sum of a span: empty → 0; otherwise first + sum of the rest.
long long sum(std::span<const int> v) {
    if (v.empty()) return 0;              // base case
    return v.front() + sum(v.subspan(1)); // progress: one element shorter
}

// x^n in O(log n) multiplications: halve n each time.
long long power(long long x, unsigned n) {
    if (n == 0) return 1;
    long long half = power(x, n / 2);     // trust it
    return n % 2 ? half * half * x : half * half;
}

int main() {
    int a[] = {3, 1, 4, 1, 5};
    std::println("sum = {}, 3^13 = {}", sum(a), power(3, 13));
}

2. The call stack is finite

Each active call keeps a stack frame: its parameters, locals, and return address. Frames of a deep recursion pile up until the function returns. The stack is small and fixed — 8 MiB here, often 1 MiB on other platforms' threads — and running out is not an exception you can catch: the program crashes (a stack overflow; ASan reports stack-overflow).

sum above uses one frame per element, so it would overflow on a few hundred thousand elements. Rules of thumb:

• depth O(log n) (binary search, power, balanced trees): always fine;
• depth O(n) for large n (lists, degenerate trees, sum): a hazard;
• depth bounded by the answer's size (backtracking on ≤ 20 items): fine.

When depth can be large, keep the state in an explicit stack — a std::vector on the heap — and loop:

#include <print>
#include <vector>

struct Node {
    int value;
    std::vector<int> children;  // indices into the node array
};

// Depth-first sum over a tree, without recursion: the vector is the call stack.
long long tree_sum(const std::vector<Node>& nodes, int root) {
    long long total = 0;
    std::vector<int> stack{root};
    while (!stack.empty()) {
        int n = stack.back();
        stack.pop_back();
        total += nodes[n].value;
        for (int c : nodes[n].children) stack.push_back(c);
    }
    return total;
}

int main() {
    // A 200,000-node chain: recursion would need 200,000 frames.
    const int n = 200'000;
    std::vector<Node> chain(n);
    for (int i = 0; i < n; ++i) {
        chain[i].value = 1;
        if (i + 1 < n) chain[i].children.push_back(i + 1);
    }
    std::println("{}", tree_sum(chain, 0));
}

3. Recursion trees and their cost

Draw each call as a node and its recursive calls as children: the recursion tree. Its total size is the running time. Naive Fibonacci makes two calls per level, so its tree has about φⁿ ≈ 1.6ⁿ nodes — exponential — even though there are only n distinct subproblems. Caching each answer the first time (memoization) collapses the tree to n nodes. Level 7's dynamic programming is that idea made systematic.

#include <cstdint>
#include <print>
#include <vector>

int calls = 0;

std::uint64_t fib(int n) {
    ++calls;
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

std::uint64_t fib_memo(int n, std::vector<std::uint64_t>& memo) {
    ++calls;
    if (n < 2) return n;
    if (memo[n] == 0) memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}

int main() {
    std::println("fib(25) = {} using {} calls", fib(25), calls);
    calls = 0;
    std::vector<std::uint64_t> memo(26);
    std::println("fib(25) = {} using {} calls (memoized)", fib_memo(25, memo), calls);
}

4. Recursive lambdas

A lambda can't name itself in its own initializer (auto f = [&]{ f(); } doesn't compile: f's type isn't known yet). C++23's deducing this gives the lambda an explicit object parameter — the closure itself — so it can call itself. Use this auto& self to avoid copying the closure on every call:

#include <print>
#include <vector>

int main() {
    std::vector<int> out;
    auto count_down = [&](this auto& self, int n) -> void {
        if (n == 0) return;
        out.push_back(n);
        self(n - 1);
    };
    count_down(4);
    std::println("{}", out);
}

The explicit return type (-> void) is needed: the lambda calls itself before its return type could be deduced from a return statement.

5. Backtracking: choose, explore, un-choose

Backtracking builds a candidate in a single shared container. At each node of the decision tree it loops over the choices; for each: choose (modify the candidate), explore (recurse), un-choose (restore it exactly). Because every branch undoes its change, a sibling starts from the same state as its predecessor.

Worked example: subsets with duplicates

Generate every distinct subset of {2, 1, 2}. Treat it as a tree: at each node, the path so far is a subset (record it), and the children add one more element after the last one used, so each set is built in one order only.

Sorting puts equal values next to each other. At one depth, a value equal to the sibling just tried would root an identical subtree, so skip it: i > start && v[i] == v[i - 1]. Using i > 0 instead would be wrong — it would also forbid taking the second 2 one level deeper, which is how {2, 2} and {1, 2, 2} are formed.

#include <algorithm>
#include <print>
#include <vector>

std::vector<std::vector<int>> subsets(std::vector<int> v) {
    std::ranges::sort(v);
    std::vector<std::vector<int>> out;
    std::vector<int> cur;
    auto go = [&](this auto& self, std::size_t start) -> void {
        out.push_back(cur);                                // every node is a subset
        for (std::size_t i = start; i < v.size(); ++i) {
            if (i > start && v[i] == v[i - 1]) continue;   // duplicate sibling
            cur.push_back(v[i]);                           // choose
            self(i + 1);                                   // explore
            cur.pop_back();                                // un-choose
        }
    };
    go(0);
    return out;
}

int main() {
    for (const auto& s : subsets({2, 1, 2})) std::println("{}", s);
}

Notice the output is already in lexicographic order: choices are tried in ascending order and each node is recorded before its children (preorder). That's a free property of the search, not an extra sort.

Faded example: distinct permutations

Permutations use every element, so instead of a start index keep a used flag per position. Duplicates again come from equal values being interchangeable. The trick: allow equal copies only in left-to-right order — skip v[i] when its equal left neighbour hasn't been used yet. Fill in the two missing pieces:

auto go = [&](this auto& self) -> void {
    if (cur.size() == v.size()) { out.push_back(cur); return; }
    for (std::size_t i = 0; i < v.size(); ++i) {
        if (used[i]) continue;
        if (/* ??? skip duplicate */) continue;
        used[i] = true; cur.push_back(v[i]);
        self();
        /* ??? */
    }
};

6. Pruning

A branch that can't lead to a valid answer should be cut as early as possible: the earlier the cut, the bigger the subtree you skip.

• combination sum: with candidates sorted, once c[i] exceeds the remaining target, every later candidate does too — break, don't continue. Recursing with the same index i (not i + 1) lets a candidate be reused.
• N-queens: place one queen per row. Before recursing, reject squares whose column, diagonal (r - c constant) or anti-diagonal (r + c constant) is already attacked. Checking only at the end means exploring all n! column orders.

#include <print>
#include <vector>

int queens(int n) {
    std::vector<bool> col(n), diag(2 * n - 1), anti(2 * n - 1);
    int count = 0;
    auto place = [&](this auto& self, int r) -> void {
        if (r == n) { ++count; return; }
        for (int c = 0; c < n; ++c) {
            int d = r - c + n - 1, a = r + c;            // offset: r - c may be negative
            if (col[c] || diag[d] || anti[a]) continue;  // prune
            col[c] = diag[d] = anti[a] = true;
            self(r + 1);
            col[c] = diag[d] = anti[a] = false;
        }
    };
    place(0);
    return count;
}

int main() {
    for (int n = 4; n <= 8; ++n) std::println("{} queens: {}", n, queens(n));
}

A faster version keeps the three sets as bitmasks: the free columns of a row are ~(cols | diag | anti), the lowest one is free & -free, and moving to the next row shifts the diagonal masks by one. Same tree, much cheaper nodes.

7. How expensive is a generator?

You can't do better than the size of the output: 2ⁿ subsets, n! permutations, each of length up to n. What you can control is wasted work — subtrees that produce nothing (prune them) or produce repeats (skip them, rather than generating everything and deduplicating with a std::set afterwards, which pays for the duplicates and then pays again to remove them).

Summary

• Recursion: base case, progress, combine — and trust the smaller call.
• Depth is a resource: O(n)-deep recursion on big inputs overflows the stack; use an explicit stack instead.
• The recursion tree's size is the cost; memoize repeated subproblems.
• Backtracking: choose → explore → un-choose, with one shared candidate.
• Sort first; skip a sibling equal to the previous one (i > start) to avoid duplicates; recurse with the same index to allow reuse.
• Prune as early as possible; output is in lexicographic order for free when choices are tried in ascending order and recorded in preorder.
• Recursive lambdas: [&](this auto& self, …) -> R { … self(…); }.