Skip to main content

Base case in recursion

JavaScriptJunior~1 min read
Suggest an edit

In short: A base case is the condition at which a recursive function stops calling itself and returns the result immediately. It stops the recursion.

Detailed explanation

In recursion, a task is divided into smaller subtasks of the same type. For the recursive process not to be infinite, it needs a stopping point - the base case. When the input reaches this "boundary of simplicity", the function does not make a recursive call and instead returns the ready value.

Signs of a good base case:

  1. Unambiguity - it is easy to tell that dividing the task further makes no sense.
  2. Completeness - the base case covers the real "edge" inputs.
  3. Reachability - every recursive step brings the arguments closer to the base case.

Examples:

  • Factorial:
javascript
function factorial(n) { if (n === 0) return 1; // base case return n * factorial(n - 1); // recursive step }
  • Array traversal:
javascript
function sum(arr, i = 0) { if (i === arr.length) return 0; // base case: empty tail return arr[i] + sum(arr, i + 1); }
  • Tree search:
javascript
function find(node, target) { if (!node) return null; // base: empty branch if (node.value === target) return node; // base: found return find(node.left, target) || find(node.right, target); }

Common mistakes:

  • No base case -> infinite recursion and stack overflow.
  • A base case exists, but the recursive step does not shrink the task (does not approach the base).
  • Incomplete base case (does not account for 0, an empty array, null, etc.).

Tips:

  • First state the base case in words, then code it.
  • Check that every recursive call makes the input "simpler".
  • For several "edges" (for example, n < 0, n === 0, n === 1), define several base cases.

Short Answer

Interview ready
Premium

A concise answer to help you respond confidently on this topic during an interview.

Suggest an edit