Pattern - Recursive Decomposition

Every recursive solution follows the same pattern: identify the smallest case (base case), then express the problem using a smaller version of itself (recursive case).

For factorial: smallest case is $n = 0$, and $n! = n \times (n-1)!$. For GCD: smallest case is $b = 0$, and GCD$(a, b)$ = GCD$(b, a \mod b)$. When you see a new problem, ask: "What's the simplest input?" and "How can I reduce a bigger input to a smaller one?" These two questions reveal most recursive solutions.

The pattern applies to strings (first character + rest), arrays (first element + rest), trees (root + subtrees), and more. You'll see this everywhere.