Recursion and Backtracking

Recursion

A recursive function solves a problem by calling itself on a smaller input. Every recursive function needs:

A base case that returns without recursing
A recursive case that moves toward the base case

The call stack uses $O(\text{depth})$ space. Overlapping subproblems (as in naive Fibonacci, which is $O(2^n)$ ) call for memoization or dynamic programming; Factorial is the simplest linear recursion, $O(n)$ time and stack space.

Backtracking

Backtracking is a traversal technique that explores all possible solutions and abandons (backtracks from) a path as soon as it fails. It is a depth-first search over a decision tree.

Recognition signals

“Find all” or “generate all” solutions that satisfy constraints
Combinatorial output: subsets, combinations, permutations, partitions
Decisions per element: include or exclude, or choose which element goes next

Generic shape

Add a choice to the current state
Recurse with the updated state
Undo the choice (pop) so the next branch starts clean
On reaching a complete solution, record a copy of the state

Tree maze. To decide whether a path exists from the root to a leaf that avoids bad nodes (for example nodes with value 0), check every possibility and backtrack on failure: a failed child returns false to its parent, and any true from a recursive call propagates upward as a found solution. When the path itself is required, push the node onto a path list before recursing and pop it if both children fail. See Tree Maze.

Subsets, combinations, permutations

	Order matters	Choice structure	Time
Subsets	No	Include or skip each element	$O(n \cdot 2^n)$ , space $O(n)$
Combinations	No	Subsets restricted to size $k$	$O(k \cdot 2^n)$ for the include/skip version, $O(k \cdot \binom{n}{k})$ for the loop version
Permutations	Yes	Pick which unused element goes next	$O(n^2 \cdot n!)$

Key things to remember:

Combinations are almost exactly subsets; the base case is “current list has $k$ elements” and recursion stops once the index passes $n$
For each element the include branch adds it, recurses, then removes it (backtrack); the exclude branch just recurses
With duplicates, sort first and, in the exclude branch, skip over equal neighbors so the same subset is not generated twice
Permutations can be built recursively: permute the remaining elements, then insert the current element into every position of each smaller permutation, building from the end of the list backwards
Copy the current list when recording a result, since it is mutated afterwards

Gotchas

Missing base case or a recursive case that does not shrink the input causes stack overflow
Forgetting to undo state after recursion leaks choices into sibling branches
Appending the mutable working list instead of a copy corrupts stored results
Output size dominates complexity ( $2^n$ subsets, $n!$ permutations); pruning invalid branches early is the main optimization

Templates

Factorial: linear recursion with a base case
Fibonacci: branching recursion, memoization
Tree Maze: backtracking on a binary tree, returning the path
Subsets: include/exclude, with and without duplicates
Combinations: choose $k$ values from $1 \dots n$
Permutations: all orderings of a list

Problems

Problem	Pattern / template
Reverse Linked List	Recursion, Factorial
Fibonacci Number	Fibonacci
Climbing Stairs	Fibonacci
Path Sum	Tree Maze
Subsets	Subsets, Tree Maze
Subsets II	Subsets (duplicates)
Combinations	Combinations
Combination Sum	Combinations, Tree Maze
Letter Combinations of a Phone Number	Combinations
Permutations	Permutations
Permutations II	Permutations (duplicates)

Binary Search Factorial