Suggest an edit

Improve this article

Refine the answer for “What is the recursive case?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

The recursive case is the part of a recursive function where it calls itself with a reduced or simplified version of the original problem. This call must make progress toward the base case and usually combines the partial result with the current state.

## In detail

Every correct recursive function has two key components: the base case (the stopping condition) and the recursive case (the step that breaks down the problem and calls the function again). The recursive case must reduce the complexity of the problem and lead to one or more further calls, after which the results of those calls are combined.

### Structure of a recursive function

- Base case: the condition under which the function no longer calls itself and immediately returns an answer (for example, an empty collection, n = 0/1, going out of bounds).
- Recursive case: the branch where the function calls itself with a simplified subproblem. Importantly, it makes verifiable progress toward the base case and, as a rule, combines the obtained sub-result with the current context.
- Progress step: a clear reduction of the problem - n → n - 1, range [l, r] → one half, a tree node → its children, a list → "head" + "tail".
- Combining results: how to get the final answer from partial answers (for example, n * factorial(n - 1), sum(left) + sum(right), concat(flatten(child))).
- A practical note (JS): tail-call optimization is not guaranteed in most environments, so deeply recursive problems are better rewritten iteratively or given a bounded depth.

### Implementation examples

#### Factorial (JavaScript)

```
function factorial(n) {
  if (n < 0) throw new Error('n must be non-negative');
  // Base case: 0! = 1, 1! = 1
  if (n === 0 || n === 1) return 1;
  // Recursive case: n! = n * (n - 1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120
```

Here the recursive case reduces n by 1 and advances toward the base case n = 1 or 0, after which the results are multiplied.

#### Tree traversal (DFS)

```
const tree = {
  value: 1,
  children: [
    { value: 2, children: [] },
    { value: 3, children: [{ value: 4, children: [] }] }
  ]
};

function dfs(node, visit) {
  // Base case: an empty node
  if (!node) return;
  visit(node);
  // Recursive case: visit each child
  for (const child of node.children || []) {
    dfs(child, visit);
  }
}

dfs(tree, n => console.log(n.value)); // 1 2 3 4
```

The recursive case calls dfs for each child node, thereby splitting the tree into subtrees.

#### Sum of a nested array

```
function sumNested(arr) {
  let sum = 0;
  for (const item of arr) {
    if (Array.isArray(item)) {
      // Recursive case: sum the sub-array
      sum += sumNested(item);
    } else {
      // Base case: a primitive number
      sum += item;
    }
  }
  return sum;
}

console.log(sumNested([1, [2, [3, 4]], 5])); // 15
```

The recursive case processes a nested array until it reaches numbers (the base case).

#### Binary search (divide and conquer)

```
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  // Base case: the range is empty
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid; // Base case: found
  // Recursive case: narrow the search to one of the halves
  if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  return binarySearch(arr, target, mid + 1, right);
}

console.log(binarySearch([1, 2, 3, 4, 5], 4)); // 3
```

The recursive case halves the range size at every step, guaranteeing progress toward the base case.

### Frequent mistakes in the recursive case

- No base case, or it is unreachable - infinite recursion and a stack overflow.
- No progress - the arguments of the recursive call do not move it closer to stopping (for example, you pass the same values).
- Exponential duplication of subproblems - the classic fib(n) without memoization (two recursive calls, large overlaps). Solution: memoization/dynamic programming or iteration.
- Forgetting to return the result of the recursive call - the function always returns undefined/an incorrect result.
- Mutating a shared structure between branches - hard-to-trace bugs. It is better to use pure functions or copies where needed.

### How to check the correctness of the recursive case

1. Clearly formulate the base case and show that it is reachable.
2. Prove progress: at every step the input becomes "smaller" (size, depth, distance, range).
3. Define an invariant - what remains true before and after the recursive step.
4. Check the combination of results: are you correctly assembling the final answer from the sub-results.
5. Assess the complexity (time and space) and avoid redundant calls (use memoization if needed).
6. Cover edge cases with tests: empty inputs, minimum/maximum values, deep nesting.

### An interview template

```
function solve(problem) {
  // 1) Base case(s)
  if (isBase(problem)) return baseAnswer(problem);

// 2) Progress: simplify the problem
  const smaller = reduce(problem);

// 3) Recursive case: solve the subproblem
  const partial = solve(smaller);

// 4) Combine the results
  return combine(problem, partial);
}
```

### When to use recursion

- Trees and graphs: traversals (DFS), computations on subtrees, path finding (tracking a set of visited nodes).
- Divide and conquer: binary search, quicksort, merging, building segment trees.
- Backtracking: search with rollback (generating permutations, N-queens, parsing).
- Problems with a naturally recursive data structure or formula (for example, recursive definitions).

### Tail recursion and iteration

Tail recursion is when the recursive call is the last operation of the function and the result is returned directly. This potentially allows the stack to be optimized, but in JavaScript such optimization is not guaranteed. For large depths, iteration or an explicit stack is preferable.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts962 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.