Recursion vs Backtracking

What Is Recursion?

A function calls itself with a smaller or simpler input. Base case stops the recursion. Used for tree/graph traversal, divide and conquer, and DP.

What Is Backtracking?

Backtracking is recursion plus "undo": you try a choice, recurse, then undo the choice to try another. Used when you need to explore all possibilities (all paths, all subsets, all permutations).

When to Use Which

• Recursion only: Compute one answer (e.g. max path sum, height of tree). No need to undo.
• Backtracking: Generate all solutions (subsets, permutations, combinations, N-Queens). Undo after each try.

Classic Backtracking Templates

Subsets

• For each element: include it, recurse, exclude it (undo), recurse.

Permutations

• For each position: try each unused element, recurse, undo.

Combinations

• Similar to subsets but with size constraint; avoid duplicates by passing a start index.

Optimization

• Pruning: stop early when the current path cannot lead to a valid solution.
• Memoization: when the same state can repeat (more DP than pure backtracking).

Summary

Recursion = reuse logic on smaller input. Backtracking = try choice, recurse, undo. Practice both on Preplume(/).