Recursion

What it is

Recursion solves a problem by identifying a smaller subproblem of the same shape, calling yourself on it, and combining that result with a small amount of local work. It underlies several different-looking techniques here: exponentiation by repeated halving, tree construction from paired traversals, exhaustive search with save-and-restore state (backtracking), and parsers that handle nested structure by recursing into each nested group. What ties them together is the recursive leap of faith — assume the recursive call on the smaller input already works, and reason only about how to build the current answer from that result.

When it applies

• The problem has an inherent recursive structure: a tree, a nested bracket/parenthesis grammar, or a mathematical recurrence where the answer at size n is built from the answer at a smaller size.
• Reversing or restructuring a linked structure where "do the rest, then fix up the front" is cleaner than tracking three pointers by hand — though check the input size against the recursion depth limit first.
• A computation can be halved rather than reduced by one each step (exponentiation, divide-and-conquer), which turns an O(n) recursion into O(log n).
• It does not apply, or needs care, when the input is large enough that the recursion depth itself becomes the bottleneck — a linked list of thousands of nodes reversed recursively can blow a language's default call-stack limit even though the algorithm is correct; the iterative equivalent is then the safer default.

Tells in the problem

• "This structure contains further instances of the same structure" (a bracket group containing another bracket group, a subtree that is itself a tree) — recurse into the nested instance and combine.
• "Reverse/build/traverse this linked structure" where describing it as "do this to the rest, then handle the current node" is more natural than an explicit loop with saved pointers.
• "Compute x^n," "compute the n-th term of a linear recurrence," or anything where doubling the input size roughly doubles the work needed for one recursive step — the halving structure signals O(log n) recursion (exponentiation by squaring) is available, not just O(n).
• "Reconstruct a tree from these two traversal orders" — a recursive split where one traversal locates the root and the other tells you how large each subtree is.
• A grammar with nesting depth that the input size doesn't bound tightly — recursive-descent parsing, where each nonterminal is a function that may call itself for a nested subexpression.

The classic mistake

The most common bug is calling the recursive function twice on the same subproblem instead of once and reusing the result — writing f(n // 2) * f(n // 2) instead of computing half = f(n // 2) and then half * half — which silently turns an O(log n) algorithm into an O(n) one while still producing the correct answer, so it passes correctness tests and only fails on a timing or scale check. The second common mistake is choosing recursion for a linear (not halving) reduction on an input large enough that the call stack itself becomes the limiting resource — a list or string with tens of thousands of elements recursed one at a time will exhaust a typical default stack depth long before it exhausts any reasonable time budget. Before committing to a recursive solution, ask whether each call meaningfully shrinks the problem (by a constant fraction, ideally) or only shrinks it by one, and check the input size against your language's practical recursion depth.

Questions to start with

• Pow(x, n) — the canonical halving recursion, and the standard trap of computing the same half twice instead of squaring it once.
• Reverse Linked List — recursion expressed as "reverse everything after me, then fix up my own link," directly contrasted with the iterative three-pointer version and its stack-depth trade-off.
• Generate Parentheses — recursion as exhaustive search (backtracking), where the recursive calls explore choices rather than shrink a single input.
• Decode String — a nested grammar where a recursive parser mirrors the input's own bracket nesting almost line for line.
• Basic Calculator — the same nested-parsing idea at greater depth, contrasted directly with an iterative stack-based version of the identical logic.