Recursion and backtracking

In short

Recursion is a problem-solving technique in which a function calls itself on a smaller instance of the same problem until it reaches a base case that can be answered directly. Backtracking is recursion applied to search: it builds a candidate solution one choice at a time, abandons ("backtracks" from) any partial candidate that cannot possibly lead to a valid solution, and so explores a pruned state-space tree instead of all combinations. Together they are the foundation of N-Queens, Sudoku, maze solving, subset and permutation generation, and are the single most common technique family in placement coding rounds (TCS NQT, Infosys HackWithInfy, Wipro, Zoho, Amazon, Microsoft, Flipkart, Oracle, Adobe) and in GATE CS questions on recurrences and call-stack behaviour. University syllabi (AICTE model curriculum, UGC CBCS "Data Structures" and "Design and Analysis of Algorithms") examine recursion tracing, recurrence formulation, stack space and the standard backtracking algorithms with their complexities.

Explained

Anatomy of a recursive function

• Every correct recursive function has two parts: one or more base cases (stopping conditions answered without recursion) and one or more recursive cases that call the function on a strictly smaller input.
• Three rules: (1) a base case must exist; (2) every recursive call must make progress towards it; (3) the function must assume its own correctness for smaller inputs (the *recursive leap of faith*, formalised as induction).
• Correctness proof is by mathematical induction: base case verified directly, recursive case assumed correct for size n−1 (or n/2) and shown to produce the right answer for n.
• Stack frame / activation record: each call allocates a frame on the call stack holding parameters, local variables, saved registers and the return address. Frames are popped in LIFO order as calls return.
• Stack overflow occurs when depth × frame size exceeds the thread stack (typically ~1 MB default in the JVM, settable with -Xss; ~8 MB main-thread stack on Linux; Python guards it with a soft limit of 1000 frames, raising RecursionError, changeable via sys.setrecursionlimit). Exact defaults vary by platform and version.
• Pending versus completed work: in return n * fact(n-1) the multiplication is *pending* after the call returns, so the frame must survive — this is what makes recursion consume O(depth) space.

Classification of recursion

• Direct - a function calls itself. Indirect / mutual - A calls B, B calls A (classic example: isEven(n) = isOdd(n−1)).
• Linear (single) recursion - one recursive call per invocation: factorial, array sum, linear search, GCD. Cost O(n) or O(log n), space O(depth).
• Tree (multiple) recursion - two or more calls per invocation: Fibonacci, Hanoi, subsets, binary-tree traversals. Cost grows exponentially unless subproblems are reused.
• Tail recursion - the recursive call is the *last* action and nothing is pending; the frame can be reused, making it equivalent to a loop. GCC/Clang perform tail-call optimisation at -O2; the JVM and CPython do not, so deep tail recursion still overflows in Java and Python.
• Head recursion - the call comes before any other work, so all processing happens while unwinding (used to print a list in reverse).
• Nested recursion - the argument of a recursive call is itself a recursive call, e.g. the Ackermann function A(m,n), which grows faster than any primitive recursive function and is a standard GATE/theory example.
• Non-tail recursion with accumulator: fact(n, acc) converts a non-tail form into a tail form, making an iterative rewrite mechanical.

Recursion versus iteration, and conversion

• Any recursion can be written iteratively and vice versa — recursion with an explicit stack is the general conversion, and that is exactly how compilers and iterative DFS/tree traversals work.
• Recursion wins where the problem is *defined* recursively: trees, grammars, nested structures, divide-and-style splits, state-space search. Iteration wins where a flat loop suffices.
• Overheads of recursion: a function call costs frame setup, argument copying and a jump; passing a large array/string by value at every level can turn an O(n) algorithm into O(n²) time and space. Pass by reference/index instead.
• Tracing technique for exams: draw the recursion tree (nodes = calls, edges = parent→child), write the parameter values on nodes and the returned values on edges; the number of nodes gives time, the longest root-to-leaf path gives space.
• When a recursion tree repeats identical subproblems, the fix is memoisation or tabulation — that is the dynamic-programming topic; recursion itself only provides the structure.

Backtracking: the method

• Definition: a systematic depth-first search of the state-space tree of partial solutions, in which a partial solution that violates a constraint is abandoned immediately and the algorithm returns to the previous decision point.
• Terminology (standard textbook, Horowitz–Sahni): *solution vector* x[1..n]; *explicit constraints* (the domain of each x[i]); *implicit constraints* (relations between components); *state-space tree*; *problem state*, *solution state*, *answer state*; *live node*, *E-node* (node being expanded), *dead node*; *bounding function* (the test that kills a node).
• Canonical template — choose, explore, un-choose:

void solve(partial P):
    if P is a complete solution:  record(P); return
    for each candidate c in choices(P):
        if isSafe(P, c):            # feasibility / bounding function
            place c in P            # choose
            solve(P)                # explore
            remove c from P         # un-choose (backtrack)

• Why it beats brute force: brute force generates every complete candidate then tests it; backtracking tests *partial* candidates, so one rejection at depth k prunes the entire subtree below it — for 8-Queens, 64C8 = 4,426,165,368 placements or 8⁸ = 16,777,216 row-wise sequences collapse to about 2,057 nodes visited.
• Two flavours: find *one* solution (return true up the chain and stop) or *all* solutions (continue after recording; no early return).
• Search strategy: backtracking is DFS with pruning on an implicit tree generated on the fly — it never stores the whole tree, so space is O(depth), which is why it is practical where BFS over the same space is not.

Design decisions that make or break a backtracking solution

• Ordering of choices - fail-first ordering (try the most constrained variable first) prunes earlier; in Sudoku, picking the cell with the fewest legal digits (MRV heuristic) is dramatically faster than scanning left-to-right.
• Incremental feasibility check - maintain colUsed[], diag1[], diag2[] arrays so isSafe is O(1) instead of O(n); in subset generation, carry the running sum rather than re-adding.
• State restoration - anything mutated before the recursive call must be undone after it; forgetting this is the commonest bug.
• Avoiding duplicate answers - sort the input and skip a[i] == a[i-1] at the same tree level (duplicate subsets/permutations); use a visited flag for permutations of distinct items.
• Symmetry breaking - restrict the first queen to the left half of the first row and double the count (even n), or fix the smallest element first in combination problems.
• Pruning by bound - in subset-sum with positive numbers, stop when sum > target, and prune when sum + remainingTotal < target.
• Limits - worst-case cost is still exponential or factorial; backtracking is a *practical* improvement, not a complexity-class improvement. Problems such as subset-sum, graph colouring and Hamiltonian cycle are NP-complete in general; N-Queens is not (one solution can be constructed directly for every n ≥ 4), yet enumerating all of its solutions stays exponential.

Backtracking compared with related techniques

• Backtracking vs branch and bound: both prune, but backtracking is depth-first and used for *feasibility* problems (any valid arrangement); branch and bound keeps a bound on the objective and may use best-first/LIFO/FIFO queues, and is used for *optimisation* (0/1 knapsack, travelling salesman, assignment).
• Backtracking vs DFS on a graph: DFS traverses an existing graph and marks nodes visited permanently; backtracking traverses an implicit tree of decisions and *un-marks* state on return.
• Backtracking vs dynamic programming: backtracking enumerates distinct configurations with no reusable overlap; DP applies when subproblems repeat and only a value (not the arrangement) is needed.
• Backtracking vs greedy: greedy commits to one choice and never revisits it; backtracking reverses choices, so it is complete (finds a solution if one exists) where greedy may not.

The standard problem set examined

• Towers of Hanoi - move n discs between three pegs, never a larger disc on a smaller one: 2^n − 1 moves, depth n.
• N-Queens - place n non-attacking queens on an n×n board; row-by-row recursion with column and two diagonal checks.
• Sudoku solver - 9×9 grid, fill empty cells with 1-9 obeying row, column and 3×3 box constraints.
• Rat in a maze / path in a grid - move in allowed directions, mark the cell, recurse, un-mark; count or list all paths.
• Subsets (power set), combinations, permutations, string permutations, balanced parentheses, letter case permutations.
• Subset sum and m-coloring - decision problems with a numeric or adjacency constraint.
• Hamiltonian cycle, Knight's tour, crossword/word-search, cryptarithmetic (SEND+MORE=MONEY), 8-puzzle, magnet/ Kakuro puzzles.
• Generate-and-test with constraints in parsers: recursive-descent parsing of a grammar is mutual recursion, and a failing alternative is a backtrack.

Key points

• Base case - the input size at which the answer is returned without a further call; missing or unreachable base case means infinite recursion and stack overflow.
• Recursive case - must reduce the problem strictly, otherwise there is no progress even with a valid base case.
• Call stack - LIFO store of activation records; recursion depth, not the number of calls, decides stack space.
• Auxiliary space - O(maximum recursion depth) × frame size; a tree recursion with 2ⁿ calls but depth n uses only O(n) stack.
• Tail recursion - nothing pending after the call, so it can be optimised into a loop; C/C++ compilers do it, Java and CPython do not.
• Recursion tree - counting its nodes gives the time; its height gives the space.
• Tree recursion - two or more self-calls per invocation; without reuse of subproblems it is exponential.
• Backtracking - DFS on a state-space tree with a bounding function that kills infeasible partial solutions early.
• Live node, E-node, dead node - a node yet to be expanded, the one being expanded, one with no unexplored feasible children.
• Choose-explore-un-choose - the three-line discipline; the un-choose step restores state for the sibling branch.
• Pruning - rejecting at depth k removes the whole subtree; this is the only reason backtracking is usable.
• Subsets = 2ⁿ, permutations = n! - the two basic sizes of a backtracking search space.
• Hanoi - 2^n − 1 moves, proved by M(n) = 2M(n−1) + 1.
• N-Queens solutions - 2 for n=4, 10 for n=5, 4 for n=6, 40 for n=7, 92 for n=8.
• Backtracking is for feasibility, branch and bound for optimisation - the standard one-line distinction asked in GATE and vivas.
• Worst case stays exponential - pruning improves the constant and the average case, not the asymptotic class.
• Duplicate handling - sort then skip equal siblings, else the same subset/permutation is emitted repeatedly.
• Iterative equivalent - every recursion can be rewritten with an explicit stack; this is the safe route for depths above ~10⁵.

Formulas and examples

(All quantities here are counts — dimensionless; space figures are in bytes/KB/MB, times in seconds at an assumed machine rate.)

Example 1 - Towers of Hanoi, n = 4.

• Recurrence: M(4) = 2M(3)+1, M(3) = 2M(2)+1, M(2) = 2M(1)+1, M(1) = 1.
• M(2) = 3, M(3) = 7, M(4) = 15 moves = 2⁴ − 1. ✔
• Maximum recursion depth = 4, so stack space is O(n) while time is O(2ⁿ).
• Legend check: 64 golden discs → 2⁶⁴ − 1 = 18,446,744,073,709,551,615 moves. At one move per second and 3.156×10⁷ s per year that is ≈ 5.8×10¹¹ years — about 584 billion years.

Example 2 - cost of naive recursion: Fibonacci.

• C(0) = C(1) = 1; C(n) = 1 + C(n−1) + C(n−2). So C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15.
• Check with the formula: F(6) = 8 → C(5) = 2×8 − 1 = 15. ✔
• For n = 40: F(41) = 165,580,141 → C(40) = 331,160,281 calls ≈ 3.3×10⁸. At ~10⁸ calls/second that is about 3 seconds, against microseconds for the O(n) loop — the standard demonstration of why repeated subproblems must be reused.

Example 3 - 4-Queens traced by hand (row by row, columns 0-3).

• Answer: 2 solutions for n = 4; the two are mirror images. Brute force would test 4⁴ = 256 row-wise sequences; the pruned tree reaches only 17 nodes — the root plus 16 placements.
• O(1) safety check: a queen at (r,c) is unsafe if col[c] || diag1[r+c] || diag2[r−c+n−1] is already set.

bool place(int r,int n){
  if(r==n){ count++; return false; }          // false = keep searching for all solutions
  for(int c=0;c<n;c++){
    int d1=r+c, d2=r-c+n-1;
    if(col[c]||diag1[d1]||diag2[d2]) continue;
    col[c]=diag1[d1]=diag2[d2]=1; pos[r]=c;   // choose
    place(r+1,n);                              // explore
    col[c]=diag1[d1]=diag2[d2]=0;              // un-choose
  }
  return false;
}

Example 4 - subset sum with pruning. Set S = {3, 34, 4, 12, 5, 2}, target T = 9.

• Full include/exclude tree: 2⁶ = 64 leaves, 2⁷ − 1 = 127 nodes.
• Sort ascending: {2, 3, 4, 5, 12, 34}. Prune when running sum > 9, and when sum + (total of remaining) < 9.
• Trace: 2 → 2+3=5 → 5+4=9 ✔ {2,3,4}. Continue: 5+5=10 > 9 prune; 2+4=6 → 6+5=11 prune; 2+5=7 → next 12 gives 19 prune; 3+4=7 prune onward; 4+5=9 ✔ {4,5}; branches reaching 12 or 34 die instantly because 12 > 9.
• Result: two subsets, {2,3,4} and {4,5}, found after visiting roughly 25 of 127 nodes — about an 80% cut from a two-line bounding function.

Example 5 - stack space and overflow. A recursive sum(1..n) whose frame is about 64 bytes (two ints, saved base pointer, return address, padding).

• Depth n = 10,000 → 640,000 bytes ≈ 0.61 MB — fits a 1 MB stack.
• Depth n = 100,000 → 6.4 MB — overflows a 1 MB JVM thread stack; Java needs -Xss16m or an iterative rewrite. CPython raises RecursionError far earlier, at depth 1000, unless the limit is raised (and raising it too far can segfault). Frame sizes are compiler- and ABI-dependent, so treat these as order-of-magnitude figures.

Where it is used

• Compilers and interpreters: recursive-descent parsers and expression evaluators in GCC, Python and in the SQL parsers inside products built by Indian IT services firms; grammar alternatives are tried and backtracked.
• Constraint and scheduling engines: workforce rostering, exam and classroom timetabling (used by Indian universities and coaching platforms), railway crew rostering, and shift planning in BPO/WFM tools — all variants of constrained search with backtracking or branch and bound.
• Puzzle and gaming products: Sudoku, crossword, Kakuro and chess-puzzle generators and solvers in Indian mobile-game studios; move generators in game AI.
• EDA, verification and solvers: SAT/SMT solvers (DPLL is backtracking search with unit propagation; CDCL adds clause learning) behind chip-design and formal-verification tools at Intel, Qualcomm, Synopsys and Cadence India centres.
• Systems and tooling: recursive directory traversal in backup, antivirus and deduplication tools; JSON/XML tree walking; regex engines (backtracking NFA matching); file-system du-style size computation.
• Hiring pipelines: recursion and backtracking questions are standard in TCS NQT/Digital, Infosys HackWithInfy, Wipro Elite, Zoho, Amazon, Microsoft, Flipkart, Adobe and Oracle rounds, and on HackerRank/HackerEarth/CodeChef assessments used by Indian recruiters; GATE CS tests recurrences, call-stack output and algorithm classification.

Interview questions

• Q: What are the two mandatory parts of a recursive function? A: At least one base case that returns without recursing, and a recursive case that calls the function on a strictly smaller input so the base case is always reached.
• Q: Why does recursion consume extra memory compared with a loop? A: Every pending call keeps a stack frame holding parameters, locals and the return address, so space grows with the maximum recursion depth.
• Q: What is tail recursion and why does it matter? A: The recursive call is the last operation with nothing pending, so the compiler can reuse the frame and turn it into a loop — C/C++ do this at -O2, but Java and CPython do not.
• Q: Does a function with 2ⁿ recursive calls need 2ⁿ stack space? A: No — stack space is proportional to the depth of the recursion tree, typically O(n), because sibling branches run one after another and their frames are freed.
• Q: How is backtracking different from plain brute force? A: Brute force generates complete candidates and tests them; backtracking tests partial candidates and discards an infeasible prefix, pruning its entire subtree.
• Q: Difference between backtracking and branch and bound? A: Backtracking is depth-first search for a feasible solution; branch and bound maintains a bound on an objective function to prune, and is used for optimisation problems like knapsack or TSP.
• Q: What is the time complexity of N-Queens and does pruning change it? A: O(n!) in the worst case for the row-wise formulation; pruning cuts the constant and the practical running time but not the asymptotic class.
• Q: How do you avoid duplicate subsets when the input has repeated elements? A: Sort the array and, at each level of the recursion, skip a candidate equal to the previous one that was already tried at that level.
• Q: Why must you undo the choice after the recursive call returns? A: Because the same state object is shared by sibling branches; leaving a stale choice makes later branches see an invalid board/path and lose valid solutions.
• Q: What is the minimum number of moves for Towers of Hanoi with 5 discs? A: 2⁵ − 1 = 31, from M(n) = 2M(n−1) + 1 with M(1) = 1.
• Q: When should recursion be converted to an explicit stack? A: When the depth can exceed the thread stack (roughly tens of thousands of frames) or the language forbids deep recursion — the conversion preserves the algorithm and moves the frames to the heap.
• Q: Is backtracking the same as DFS? A: It is DFS over an implicit state-space tree with a feasibility test, and unlike graph DFS it un-marks state on the way back so other branches can reuse it.
• Q: Which ordering heuristic speeds up a Sudoku solver most? A: Minimum-remaining-values — fill the empty cell with the fewest legal digits first, so contradictions surface near the top of the tree.

Common mistakes

• Writing a base case that the recursion can never reach (for example decrementing by 2 from an odd number with if (n == 0)), giving infinite recursion and a stack overflow.
• Forgetting the un-choose step, so the board, visited array or path keeps state from an abandoned branch.
• Returning true as soon as one solution is found when the question asked for *all* solutions, or continuing to search when it asked for one.
• Passing arrays, strings or vectors by value at each level, turning an O(2ⁿ) search into O(2ⁿ·n) extra copying and risking memory blow-up.
• Confusing time with space in exams: counting 2ⁿ nodes and writing O(2ⁿ) auxiliary space instead of O(n) depth.
• Recording a solution by storing the reference to the mutable working array instead of a copy — all recorded answers end up identical (usually empty).
• Claiming backtracking makes an NP-hard problem polynomial, or quoting the pruned node count as the worst-case complexity.
• Checking feasibility only at the leaves (generate-and-test), which removes all pruning and is simply brute force in recursive clothing.

Related topics

Time and space complexity · Divide and conquer · Dynamic programming · Graph algorithms: BFS, DFS and shortest paths · Greedy algorithms · DSA interview patterns