Recursion Pattern

Why this pattern matters for LeetCode

Beginners avoid recursion because the call stack feels like magic. The mental shift is this: you don't need to trace through every recursive call. You only need to answer two questions — what is the base case (when do I stop?) and what does one recursive step do (how does the answer for size n build from the answer for size n-1)? Get those two right and the language handles the rest.

What the Recursion pattern is

A recursive function solves a problem by calling itself with a smaller or simpler input. It always has a base case that returns directly without recursing (the stopping condition) and a recursive case that reduces the problem and delegates to the function itself. The call stack automatically tracks where to return after each recursive call. Recursion excels when the problem has a natural self-similar structure — trees, sequences, and combination problems all fit this shape.

Reach for Recursion when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Recursion

• ✓Tree problems where each node applies the same logic (maximum depth, path sum, inversion)
• ✓Generating all combinations or permutations (backtracking)
• ✓Divide and conquer — split the problem, solve each half, combine
• ✓Problems with a natural recurrence: f(n) = f(n-1) + f(n-2), f(n) = f(n-1) + current element
• ✓Graph DFS where the recursive call stack manages the path automatically

When NOT to use Recursion

• ✕The recursion depth could exceed ~10,000 — JavaScript will throw a stack overflow
• ✕A simple loop would be clearer and equally correct
• ✕You need to memoize results to avoid recomputation — that is the Memoization pattern
• ✕The problem has no self-similar substructure — forcing recursion makes the code harder to read

Better alternative: In those cases, an iterative loop with an explicit stack (for DFS), or memoization (for overlapping subproblems), is more appropriate.

JavaScript code template

Fibonacci and tree depth — the two foundational recursion shapes

// Classic recurrence: f(n) = f(n-1) + f(n-2)
function fib(n) {
  if (n <= 1) return n;          // base case
  return fib(n - 1) + fib(n - 2); // recursive case
}

// Tree recursion: ask left subtree, ask right subtree, combine
function maxDepth(root) {
  if (root === null) return 0;   // base case: empty node has depth 0
  const left  = maxDepth(root.left);
  const right = maxDepth(root.right);
  return 1 + Math.max(left, right); // current node adds 1
}

Both functions answer the same question — 'what is the base case?' (n <= 1 returns n; null returns 0) and 'how does this step build from the smaller answers?' (sum the two previous fibs; add 1 to the deeper subtree). You never trace through all the calls. You trust that the base case stops the recursion and the recursive case correctly reduces the problem.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Identify the base case — the smallest input where the answer is obvious and direct (empty tree, n === 0, empty string).
2. 2Identify the recursive case — how does the answer for the current input relate to the answer for a smaller input?
3. 3Write the base case first so the function always has a stopping condition.
4. 4Write the recursive call, passing a strictly smaller or simpler input each time.
5. 5Combine the result of the recursive call with the current step's contribution.
6. 6Trust the function — don't try to mentally trace every call. Verify the base case and the one recursive step.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Maximum Depth of Binary Tree

  Ask left and right subtrees for their depth, add 1 for the current node — the textbook tree recursion shape.

  Premium→
• Same Tree

  Two trees are the same if their roots match and both subtrees are recursively the same.

  Premium→
• Invert Binary Tree

  Swap left and right children at each node, then recursively invert both subtrees.

  Premium→
• Climbing Stairs

  f(n) = f(n-1) + f(n-2) — the canonical linear recurrence, base cases are f(1) = 1 and f(2) = 2.

  Premium→

Common mistakes beginners make

• ✕Missing the base case — the function recurses forever and crashes with a stack overflow. Always write the base case first.
• ✕Recursive call doesn't reduce the problem — if you call fib(n) inside fib(n), the input never gets smaller. Every recursive call must move toward the base case.
• ✕Returning inside the recursive call without combining — `return fib(n-1)` discards fib(n-2). Make sure you use the return value.
• ✕Trying to trace all the calls mentally — you don't need to. Verify the base case is correct and the single recursive step is correct. The induction takes care of the rest.

Recursion vs Iteration

Choose the right tool for the job.

Time and space complexity

Each recursive call adds one frame to the call stack. A linear recursion (f(n) calls f(n-1)) uses O(n) stack space. A tree recursion (f(n) calls f(n-1) and f(n-2)) also uses O(n) stack space — the deepest branch determines the stack depth, not the total number of calls. Time complexity depends on how many recursive calls fire and what each does.

Frequently asked questions

How do I know when to use recursion vs a loop?

Use recursion when the problem has self-similar structure: trees, nested data, unknown depth of branching. Use a loop when processing a flat sequence from start to finish. If you'd need a stack to simulate the recursion anyway (like iterative DFS), the recursive version is usually cleaner.

Why does my recursive function cause a stack overflow?

Either the base case is missing (the function never stops) or the recursive call doesn't reduce the problem toward the base case. Check both. Also, deeply recursive functions on large inputs (n > 10,000) will exceed JavaScript's call stack limit — switch to iteration with an explicit stack in that case.

Do I have to trace through every recursive call to understand the answer?

No, and trying to will confuse you. Verify two things: (1) the base case returns the correct answer directly, and (2) the recursive step is correct assuming the inner call returns the right answer. That's inductive reasoning — if both are true, the whole function is correct by induction.

What is the call stack and why does it matter for recursion?

The call stack is where the runtime records where to return after each function call. Each recursive call pushes a new frame onto the stack. When the base case returns, the frames pop one by one. The stack depth equals the maximum number of recursive calls waiting at once. Deep recursion = large stack = potential overflow.