What Recursion Is

Recursion is a problem-solving technique in programming where a function calls itself to solve smaller instances of the same problem.

Instead of completing a repetitive task using a loop construct (for or while), a recursive function breaks the input down into a smaller piece, processes that piece, and invokes itself on what remains until it reaches a natural stopping condition.

The function's work includes another call to that same function. This self-calling behavior is the defining feature of recursion.

Where recursion is used

Recursion isn't just theory—it powers tools you use every day. It is the go-to approach whenever data is nested, branched, or structured like a tree.

Common real-world examples include:

• Nested JSON (JSON.parse / JSON.stringify): Objects can contain arrays with more objects inside them. Recursion unwraps each layer, no matter how deep.
• HTML DOM Trees: Web pages are trees of elements (<div> inside <div>). Finding, reading, or styling nested elements is naturally recursive.
• File Systems & Folders: A folder can hold files and other folders, which have their own folders. Recursion searches through them without needing to know how deep they go.
• Deep Object Copying: Cloning complex objects (structuredClone), flattening nested data, or reading configuration files.
• Trees & Graphs: Searching binary trees, crawling links on the web, or finding connections in social networks and map routes.

The Two Essential Ingredients

Every valid recursive function requires two core parts to work correctly:

1. The Base Case: The condition under which the function stops calling itself and returns a result directly. Without a base case, the function calls itself indefinitely until the system runs out of memory (a stack overflow).
2. Progress (Different Input): Each recursive call must modify the input and send a smaller, simpler piece of data toward the base case.

If either ingredient is missing, the recursion fails:

• Missing Base Case $\rightarrow$ Infinite loop leading to RangeError: Maximum call stack size exceeded / RecursionError.
• Missing Progress $\rightarrow$ The function keeps passing the same input forever, never reaching the base case.

The Call Stack

The call stack tracks active JavaScript function calls. It shows which invoked function is currently running and which function should resume afterward.

Adding function calls

When JavaScript invokes a function, it pushes that function onto the call stack. A pushed function becomes the current function being executed.

If that function invokes another function, JavaScript pushes the newly invoked function on top of it. The most recently invoked function is therefore at the top of the stack.

Removing function calls

When a function returns, JavaScript removes it from the call stack. Execution then resumes in the function that is now on top of the stack.

This continues until each invoked function has returned and been removed.

Recursive Pattern: Countdown

Let's examine the simplest example of recursion: a function that counts down from a number $n$ to $1$, and then stops.

A recursive countdown function implements both required parts:

1. Base case: Stop when $n \le 0$.
2. Progress: Send $n - 1$ to the next call.

countdown(n):
  if n <= 0:
    return

  print n
  countdown(n - 1)

The input becomes smaller on every call. When it reaches 0, the base case triggers and halts execution.

Implementation

function countdown(n) {
  // 1. Base Case: stops recursion
  if (n <= 0) {
    console.log("Blast off!");
    return;
  }

  // 2. Work: print current value
  console.log(n);

  // 3. Progress: call self with smaller input
  countdown(n - 1);
}

countdown(3);
// Output:
// 3
// 2
// 1
// Blast off!

Classic Recursion Examples

1. Sum of a Range (sumRange)

Suppose we want to calculate the sum of all consecutive integers from $1$ up to $n$. For example:

• sumRange(3) $\rightarrow 3 + 2 + 1 = 6$
• sumRange(4) $\rightarrow 4 + 3 + 2 + 1 = 10$

Notice the recursive subproblem: $\text{sumRange}(n) = n + \text{sumRange}(n - 1)$. The smallest known answer is $\text{sumRange}(1) = 1$, which serves as our base case.

function sumRange(n) {
  // Base case
  if (n === 1) return 1;

  // Recursive call with smaller input
  return n + sumRange(n - 1);
}

console.log(sumRange(3)); // 6

2. Factorial (factorial)

The factorial of a non-negative integer $n$ (written as $n!$) is the product of all positive integers less than or equal to $n$:

$4! = 4 \times 3 \times 2 \times 1 = 24$

By definition, $0! = 1$ and $1! = 1$. The recursive relationship is:

$n! = n \times (n - 1)!$

function factorial(n) {
  // Base case: 0! and 1! both equal 1
  if (n <= 1) return 1;

  // Recursive step: n * factorial(n - 1)
  return n * factorial(n - 1);
}

console.log(factorial(4)); // 24
console.log(factorial(5)); // 120

3. Traversing Nested Data (Real-World Example)

Imagine you receive an array of numbers that contains other nested arrays at unpredictable depths:

const numbers = [1, [2, [3, 4], 5], 6];

Calculating the total sum with regular loops is cumbersome because the nesting depth is unknown. With recursion, each element is either a number (base case) or another array to recurse through:

function sumNested(items) {
  let total = 0;

  for (const item of items) {
    if (Array.isArray(item)) {
      // Recursive step: process the nested array
      total += sumNested(item);
    } else {
      // Base item: directly add the number
      total += item;
    }
  }

  return total;
}

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

Collecting Results Recursively

To collect odd values from an array, recursion can process the array while leaving the original unchanged. Two common approaches are helper method recursion and pure recursion.

Helper method recursion

An outer function defines the accumulator array, while an inner recursive helper function populates it as it processes the input:

function collectOddValues(arr) {
  const results = [];

  function helper(helperInput) {
    // Base case: all elements processed
    if (helperInput.length === 0) {
      return;
    }

    // Work: collect odd number
    if (helperInput[0] % 2 !== 0) {
      results.push(helperInput[0]);
    }

    // Progress: recurse with remaining elements
    helper(helperInput.slice(1));
  }

  helper(arr);
  return results;
}

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

Pure recursion

Pure recursion is completely self-contained—each recursive call creates and returns its own results, which are combined as the call stack unwinds:

function collectOddValues(arr) {
  let results = [];

  // Base case: empty array
  if (arr.length === 0) {
    return results;
  }

  // Work: collect odd number
  if (arr[0] % 2 !== 0) {
    results.push(arr[0]);
  }

  // Progress: combine with recursive call on remaining elements
  results = results.concat(collectOddValues(arr.slice(1)));

  return results;
}

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

Comparison

Both approaches collect odd values recursively and do not mutate the original array.

Common Recursion Errors

Recursive code can fail with a maximum call stack error. Three common causes are missing - base cases, incorrect recursive calls, and missing returns.

1. Check the base case

A base case determines when recursion stops. If it is missing, the recursive process can continue until a maximum call stack error occurs.

When diagnosing the function, first confirm that a base case exists.

2. Check the recursive call

Inspect the recursive call carefully. An incorrect recursive call can prevent the function from reaching its stopping condition and lead to a maximum call stack error.

Ask:

• Is the recursive call the intended call?
• Does the call match the function’s recursive logic?

3. Check return statements

A missing return is another common recursion error. If the recursive result must be passed back, verify that the function returns it.

Recursion vs. Iteration

Every recursive problem can theoretically be solved iteratively using loops, and vice versa. Understanding their trade-offs helps you choose the right approach:

Key Takeaways

• Self-Calling Function: Recursion occurs when a function calls itself to solve smaller subproblems of the same type.
• The Two Non-Negotiables: Every recursive function must have a base case to stop execution and a progress step that moves input closer to that base case.
• Real-World Ubiquity: Recursion powers core software engineering tasks including JSON parsing, DOM traversal, file system navigation, and tree/graph processing.
• Call Stack Cost: Unlike iterative loops, every recursive call consumes a frame on the call stack. Always ensure a reachable base case to prevent stack overflows.