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.

#Trees: the structure that is recursion made visible

A tree is a node with children that are themselves trees, so almost every tree algorithm is three lines of recursion: do something with this node, recurse into the children, combine. The only decision is when the node's own work happens relative to its children, and that decision has names:

record Node(int value, Node left, Node right) {}
 
void preorder(Node n, List<Integer> out)  { if (n == null) return; out.add(n.value()); preorder(n.left(), out);  preorder(n.right(), out); }
void inorder(Node n, List<Integer> out)   { if (n == null) return; inorder(n.left(), out);  out.add(n.value()); inorder(n.right(), out); }
void postorder(Node n, List<Integer> out) { if (n == null) return; postorder(n.left(), out); postorder(n.right(), out); out.add(n.value()); }

Pre-order is "me, then my children": copying a tree, serialising it, printing a directory listing. In-order on a binary search tree visits the values in sorted order, which is the property that makes TreeMap iteration sorted and is the answer to "k-th smallest". Post-order is "my children, then me": computing a directory's size, freeing a tree, evaluating an expression tree where the operator needs its operands first, and every "height of this subtree" computation:

int height(Node n) { return n == null ? 0 : 1 + Math.max(height(n.left()), height(n.right())); }   // post-order in disguise

The fourth traversal is level order, and it is not recursion at all: it is the BFS from the next lesson with a queue, visiting the root, then both children, then all four grandchildren — the shape for "print by depth", "the widest level", and "the nearest node that satisfies X".

Two things a backend engineer meets more often than a balanced-tree rotation. The recursion depth is the tree's height, so a degenerate tree — a linked list wearing a tree's record — recurses n deep and hits the stack limit from the previous section on a large enough input, which is why the JDK's TreeMap is red-black and why a JSON document nested ten thousand levels deep is a denial-of-service against a recursive parser. And the lowest common ancestor of two nodes, which is post-order with a return value: return the node if it is one of the two, otherwise the non-null result of the children, or the node itself if both children returned something. It is the shape of "the nearest shared package of two classes", "the closest common manager", "the merge base of two branches" — the git course's graph is a tree in the common case, and git merge-base is this algorithm on it.

#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; }