Recursion is a function that calls itself with a smaller problem. It sounds circular but it works because every recursive call gets closer to a base case — a problem so small it has a direct answer.

Three-part recipe:

1. Base case — what's the smallest problem? (array of 0 or 1 elements)
2. Recursive case — reduce the problem (call with a smaller input)
3. Combine — use the recursive result to build the full answer

function factorial(n: number): number {
  if (n <= 1) return 1;            // base case
  return n * factorial(n - 1);    // recursive case + combine
}
// factorial(4) → 4 * factorial(3) → 4 * 3 * factorial(2) → ... → 24

The two beginner mistakes

Missing or unreachable base case → infinite recursion → stack overflow. Before writing the recursive case, write the base case and convince yourself every call moves toward it.

Shrinking the problem expensively. arr.slice(1) copies the whole rest of the array — O(n) per call, O(n²) total. Pass an index instead and the array is never copied:

// ❌ O(n²): every call copies the array
function sum(arr: number[]): number {
  if (arr.length === 0) return 0;
  return arr[0] + sum(arr.slice(1));
}

// ✓ O(n): same recursion, zero copies
function sumFrom(arr: number[], i = 0): number {
  if (i === arr.length) return 0;
  return arr[i] + sumFrom(arr, i + 1);
}

Why it matters for DSA: Trees are inherently recursive structures. Every tree algorithm (DFS, BFS helpers, tree DP) uses recursion. Understanding recursion deeply = understanding trees, graphs, and divide-and-conquer.