Recursion and backtracking

Recursion solves a problem by reducing it to smaller calls with a base case. Backtracking explores a tree of choices, records a candidate, recurses, and then undoes the choice. It fits permutations, combinations, subsets, path search, and constraint satisfaction.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Good answers define the state, choices, stopping condition, and pruning rule before code. They also mention stack depth and whether iterative traversal would be safer.

Common pitfalls: Shared mutable arrays must be copied when saving results. Forgetting to undo state contaminates later branches. Missing base cases cause infinite recursion.

Checklist:

• Name state and choices.
• Write the base case.
• Undo mutations.
• Prune impossible branches.