Recursion and backtracking

Recursion is a function that calls itself, and the reason it is worth learning is not elegance — it is that some structures are defined recursively, and code shaped like the data is code you can reason about. A tree has subtrees. A directory has directories. A JSON object has objects.

#Two parts, and one of them is where the bugs are

static long factorial(int n) {
    if (n <= 1) return 1;            // base case: stops
    return n * factorial(n - 1);     // recursive case: moves towards it
}

Every recursion needs both, and the second half of the second requirement is the one people get wrong. It is not enough to have a base case — every recursive call must move towards it. factorial(n) calling factorial(n) has a perfectly good base case and never reaches it.

#The stack is a resource you are spending

The space-complexity lesson made this point; here is the number:

### plain recursion overflowed at depth 45524

Forty-five thousand frames on a default stack. That is a real ceiling, and it is why:

• Recursing over a collection is a bug waiting for a big collection. A recursive sum over a list of a hundred thousand elements will not survive.
• Recursing over a tree is usually fine, because a balanced tree of a million nodes is only twenty deep. Balanced is doing work in that sentence — a degenerate tree is a linked list, and the depth is n again.

Java does not eliminate tail calls. Writing the recursive call as the last statement does not help, there is no flag, and the JVM does not plan to. So in Java, a deep recursion is a loop that has not been written yet, and -Xss is a workaround rather than a fix.

#Backtracking: search that undoes its own moves

Backtracking is recursion where each step makes a choice, explores, and then takes the choice back:

void permute(List<Integer> chosen, boolean[] used, int[] xs, List<List<Integer>> out) {
    if (chosen.size() == xs.length) { out.add(new ArrayList<>(chosen)); return; }
    for (int i = 0; i < xs.length; i++) {
        if (used[i]) continue;
        chosen.add(xs[i]); used[i] = true;      // choose
        permute(chosen, used, xs, out);         // explore
        chosen.remove(chosen.size()-1); used[i] = false;   // UNDO
    }
}

The three lines in that loop are the whole pattern, and the undo is what makes it backtracking. Without it you are not searching a tree of possibilities; you are corrupting one path with another's state.

Note new ArrayList<>(chosen) when recording a result. chosen is about to be mutated by the undo, so storing the reference stores a list that will be empty by the end — the pass-by-value lesson's point arriving as a wrong answer rather than a compile error.

#Pruning is the difference between usable and not

Backtracking explores an exponential space. What makes it practical is not exploring branches that cannot work:

if (currentSum > target) return;          // every extension only adds more

That single line can turn hours into milliseconds, and it is where nearly all the engineering in a backtracking solution lives. N-queens is the standard example: checking whether a queen is attacked before placing it prunes almost the entire tree, and without it the problem is intractable at n = 12.

The question to ask at every step is: is there any way this branch still leads to an answer? If not, return now.

#Converting to iteration

Any recursion can become a loop with an explicit stack, and the conversion is mechanical: what was a call frame becomes an object you push.

Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
    Node n = stack.pop();
    // ... visit
    for (Node child : n.children) stack.push(child);
}

Worth doing when the depth can exceed the stack, and worth not doing otherwise — the recursive version of a tree walk is shorter and clearer, and clarity is the reason to use recursion at all.

Tail-recursive shapes convert to a plain loop with no stack, which is the ideal case and exactly what other languages do for you:

// recursive
static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
// the same thing, iteratively
static int gcd(int a, int b) { while (b != 0) { int t = b; b = a % b; a = t; } return a; }