Suggest an edit

Improve this article

Refine the answer for “What is the base case of recursion?”. 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 base case of recursion is the condition under which a recursive function stops making further calls and returns a direct result. It guarantees that the algorithm terminates and is correct on minimally simple inputs.

## Detailed explanation

In recursive algorithms, solving a problem is reduced to solving the same problem, but for a smaller or simpler input. The base case defines the minimal input at which the recursion must stop and what answer must be returned without further decomposition.

- A stopping condition: a logical check under which the function does not make a recursive call.
- Returning a simple result: the answer is known directly (for example, an empty collection, zero, one, a null node).
- Reachability: every recursive step must move the input closer to the base case.
- Covering edge values: the base case correctly handles minimal/empty inputs.
- Multiple base cases are possible: for example, for Fibonacci numbers, n = 0 and n = 1.

## Why the base case matters

- Guaranteed termination: without it, recursion can become infinite and overflow the stack.
- Correctness: it provides the correct answer for the minimal subproblems, on which the inductive proof is built.
- Performance: a base case that is too narrow or unreachable leads to unnecessary work.
- Safety: it prevents stack overflows and runtime errors.

## Implementation examples

### Factorial (JS)

```javascript
function factorial(n) {
  if (n < 0) throw new Error('n must be >= 0');
  if (n === 0 || n === 1) return 1; // base case
  return n * factorial(n - 1);      // recursive step
}

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

Base case: n === 0 or n === 1. The recursive step reduces n and makes the base reachable.

### Sum of array elements (JS)

```javascript
function sum(arr) {
  if (arr.length === 0) return 0; // base case
  const [head, ...tail] = arr;
  return head + sum(tail);        // recursive step
}

console.log(sum([1,2,3,4])); // 10
```

Base case: an empty array gives 0. Every step shrinks the array, bringing it closer to empty.

### GCD (Euclid's algorithm)

```javascript
function gcd(a, b) {
  if (b === 0) return Math.abs(a); // base case
  return gcd(b, a % b);             // recursive step
}

console.log(gcd(48, 18)); // 6
```

Base case: when the second argument is 0, the answer is known directly.

### Multiple base cases: Fibonacci numbers

```javascript
function fib(n) {
  if (n < 0) throw new Error('n must be >= 0');
  if (n === 0) return 0; // base case 1
  if (n === 1) return 1; // base case 2
  return fib(n - 1) + fib(n - 2);
}

console.log(fib(6)); // 8
```

Here there are two base cases: for n = 0 and n = 1. Without them, the recursion would not terminate. In practice, memoization or iteration is used for efficiency.

## Typical mistakes

- No base case, or it is not checked first.
- An unreachable base case: the parameter does not move toward the base (for example, n keeps increasing).
- A base case that is too narrow: it does not handle all boundary values (for example, only n === 0, but not n === 1).
- Side effects before checking the base: logging/changing state before making sure recursion is not needed.

## How to design a base case

1. Identify the minimal input of the problem: an empty structure, zero size, zero depth.
2. Formulate the answer for that minimal input without recursion.
3. Make sure every recursive step reduces the "size" of the problem and reaches the base.
4. Check the edge cases: empty, zero, single-element inputs.
5. Test on small data, where the execution flow is easy to trace.

## The base case in data structures

In recursive traversals of structures, the base is usually the "empty" form of the structure:

- Lists/arrays: an empty list/array, or an index that has gone out of bounds.
- Trees: a null node (the absence of a child).
- Graphs: a vertex that has already been visited (to stop repeated traversals).
- Ranges (divide-and-conquer): an empty range, or one of length 1 (for example, length < 2).

### Binary tree traversal (JS)

```javascript
function inorder(node) {
  if (node == null) return; // base case: an empty node
  inorder(node.left);
  console.log(node.value);
  inorder(node.right);
}
```

The base case stops the descent once a missing child node is reached.

## Summary

The base case is a clear and reachable stopping condition for recursion, with a direct answer. Design it based on the minimal input, check it first, and make sure every recursive step makes it reachable. Use multiple base cases where needed.

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.