Recursion solves a problem by solving a smaller version of itself. Backtracking explores choices, undoing each one that leads to a dead end. Together they power tree traversals, combinatorial search, and constraint solving.
Every fib(n) call spawns two more. Without memoization, the same subproblems are solved over and over — dashed nodes are redundant. Toggle memo to see how caching eliminates the repeated work.
15 calls without memo · 9 with memo
Compute fib(5) recursively. Watch for repeated work.
Your brain tries to trace every recursive call at once. Don't. Trust that the recursive call returns the right answer for the smaller input, then combine. Think about one level at a time, not the whole tree.
To generate all subsets, make a binary choice at each element: include it or skip it. The decision tree has 2n leaves, one per subset. Watch the path advance and backtrack.
Generate all subsets of [1, 2, 3]. At each element, include or skip.
Recursive template
function solve(problem) { if (baseCase) return baseSolution // break into smaller pieces const sub = solve(smallerProblem) return combine(sub) }
Backtracking — choose / explore / unchoose
function backtrack(path, choices) { if (isSolution(path)){ results.push([...path]) return } for (const c of choices) { path.push(c) // choose backtrack(path, next) // explore path.pop() // unchoose } }
O(2ⁿ) or O(n!) time — exponential by nature