Recursion

Recursion is one of the most fundamental ideas in computer science, yet it is also one of the most misunderstood. At a surface level, recursion is simply the ability of a function to call itself. At a deeper level, however, recursion is a model of computation that allows us to describe complex behavior in terms of simpler, self-similar subproblems.

From a theoretical perspective, recursion does not provide additional expressive power compared to iteration. Any recursive algorithm can be rewritten using loops and explicit state, typically by simulating the call stack manually. The choice between recursion and iteration is therefore not about what can be computed, but about how clearly a problem’s structure is expressed. In many cases, recursion makes that structure explicit and easier to reason about.

A recursive algorithm is built around two complementary ideas. The first is a base case, which represents the simplest instance of the problem and can be solved directly. The second is a recursive step, which reduces the original problem to one or more smaller instances of the same problem. Correct recursive reasoning depends on the guarantee that each recursive step makes measurable progress toward a base case, ensuring termination.

In practice, recursion is closely tied to the call stack. Each function invocation creates a new stack frame that stores local variables and return addresses. Understanding recursion therefore requires understanding how the call stack evolves over time, not just how values are computed. This execution model has concrete implications: recursive solutions consume stack space, have limits on depth, and may behave very differently across languages and runtimes.

Some recursive functions are tail-recursive, meaning that the recursive call is the last operation performed by the function. In languages or runtimes that support tail-call optimization, such functions can be executed using constant stack space, effectively behaving like loops. However, in JavaScript and TypeScript, tail-call optimization is not reliably applied, so recursive depth must always be considered explicitly.

The Anatomy of a Recursive Function

Every recursive function, regardless of complexity, follows the same fundamental structure. Understanding this structure is essential not only for writing correct recursive code, but also for reasoning about its correctness, termination, and complexity.

At its core, a recursive function is defined by three elements: a base case, a recursive case, and a notion of progress.

The base case represents the simplest instance of the problem, one that can be solved directly without further recursion. It acts as an anchor point for the computation. Without a base case, recursion has no stopping condition and will inevitably lead to infinite recursion.

The recursive case defines how the problem is reduced to one or more smaller instances of the same problem. This reduction must preserve the structure of the original problem while moving closer to the base case.

Equally important, though often implicit, is the idea of progress. Each recursive call must operate on a strictly smaller or simpler input according to some well-defined measure. This measure is what guarantees that the recursion will eventually terminate.

To make these ideas concrete, consider the following simple recursive function:

function sum(n: number): number {
  if (n === 0) {
    return 0; // base case
  }

  return n + sum(n - 1); // recursive case
}

Here, the progress measure is the value of n. Each recursive call reduces n by one, and the recursion terminates when n reaches zero.

Recursion and the Call Stack

While recursion is often explained in terms of mathematical definitions, it is executed through a very concrete mechanism: the call stack.

Each time a recursive function is invoked, a new stack frame is created. This frame contains the function’s local variables and the information needed to resume execution after the recursive call returns. As recursion deepens, stack frames accumulate. When a base case is reached, the call stack begins to unwind, returning values back through the chain of calls.

Understanding this stack-based execution model is crucial. Many bugs in recursive code arise not from incorrect logic, but from an incomplete mental model of how values flow back up the call stack.

To help build this intuition, the following interactive visualization shows how stack frames are created and resolved during a recursive computation.

Notice how the base case does not “stay” on the stack. It immediately produces a value, and the stack starts unwinding. Recursive results are not computed while descending, but while returning.

Recursive Reasoning

When reasoning about a recursive function, it is often useful to think in terms of assumptions. Instead of tracing the entire execution, we assume that the recursive call correctly solves a smaller version of the problem, and then focus on how the current step uses that result.

In the sum example, we assume that sum(n - 1) correctly computes the sum of all integers from 0 to n - 1. Given that assumption, it becomes straightforward to see why adding n produces the correct result for sum(n).

This style of reasoning mirrors mathematical induction and forms the foundation for proving the correctness of recursive algorithms. It will reappear throughout this article as we explore structural recursion, divide-and-conquer strategies, and recursive parsing.

Structural Recursion

One of the most important uses of recursion arises when a problem is defined over a recursive data structure. In these cases, recursion is not merely a convenient implementation choice, but a direct reflection of the structure of the data itself. This style of problem solving is known as structural recursion.

A data structure is recursive when it is defined in terms of smaller instances of the same structure. A linked list is a classic example: a list is either empty, or it consists of a value followed by another list. Trees, graphs with recursive definitions, and many abstract syntax structures share this property.

When data is defined recursively, functions that operate on that data often follow the same shape. The base case of the function corresponds to the simplest form of the data, while the recursive case mirrors how the structure is composed.

Consider for example a singly linked list. Conceptually, it can be described as:

• an empty list, or
• a node containing a value and a reference to another list

This definition immediately suggests a recursive way to process the list. Any operation on the list can be expressed as:

• handle the current node
• recursively process the remainder of the list

This correspondence between data definition and function definition is the essence of structural recursion. As an example, consider the problem of merging two sorted linked lists. Rather than thinking in terms of pointers and iteration, we can reason recursively: the merged list starts with the smaller of the two head values, followed by the merge of the remaining elements.

class ListNode {
  val: number;
  next: ListNode | null;

  constructor(val: number, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeTwoLists(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  if (l1 === null) { 
    return l2;
  }
  
  if (l2 === null) {
    return l1;
  }

  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
}

The base cases handle empty lists directly. The recursive step reduces the problem size by advancing exactly one node in one of the lists. Each recursive call operates on strictly smaller input, guaranteeing termination.

Reasoning About Correctness

Structural recursion lends itself naturally to correctness arguments. If we assume that the recursive call correctly merges the tails of the lists, then the correctness of the current step follows immediately by choosing the smaller head element.

This form of reasoning is closely related to structural induction, where correctness is shown by proving that:

• the function works for the simplest form of the structure
• assuming it works for smaller substructures, it also works for larger ones

Although a full formal proof is often unnecessary in practice, having this mental model is extremely useful. It allows us to focus on local correctness at each step, rather than attempting to reason about the entire execution at once.

When Structural Recursion Shines

Structural recursion is particularly effective when:

• the data structure is recursively defined
• each recursive step naturally consumes part of the structure
• the problem can be decomposed without additional global state

In these situations, recursive solutions tend to be concise, expressive, and closely aligned with the problem definition. As we will see in later sections, this alignment between data and computation is one of the strongest arguments in favor of recursion as a modeling tool.

Divide & Conquer

Divide and Conquer is a problem-solving paradigm that is most naturally expressed using recursion. The core idea is to break a problem into smaller subproblems of the same type, solve each subproblem independently, and then combine their results to obtain the solution to the original problem.

While Divide and Conquer is often presented as a separate topic, it is best understood as a structured form of recursion. What distinguishes it from simpler recursive patterns is that each recursive step typically generates multiple subproblems, leading to a branching recursion tree rather than a single chain of calls.

Conceptually, a Divide and Conquer algorithm consists of three phases:

• Divide the problem into smaller subproblems.
• Conquer each subproblem recursively.
• Combine the results of the subproblems.

The correctness and efficiency of such algorithms depend on how effectively the problem size is reduced at each step and how expensive the combination phase is.

Divide & Conquer on Mathematical Problems

A classic example is the computation of powers. The value of $x^n$ can be defined recursively as:

• $x^0 = 1$
• $x^n = (x^{n/2})^2$ if $n$ is even
• $x^n = x \cdot x^{n-1}$ if $n$ is odd

This definition leads directly to a recursive algorithm that reduces the exponent by half at each step, resulting in logarithmic recursion depth.

function pow(x: number, n: number): number {
  if (n === 0) return 1;

  if (n < 0) {
    return 1 / pow(x, -n);
  }

  const half = pow(x, Math.floor(n / 2));

  if (n % 2 === 0) {
    return half * half;
  }

  return half * half * x;
}

Unlike linear recursion, where each call reduces the problem by a constant amount, this approach dramatically reduces the number of recursive calls. The recursion tree has height $O(\log n)$, and each level performs constant work.

To reason about Divide and Conquer algorithms, it is often useful to visualize the recursion tree. Each node represents a recursive call, while its children represent the subproblems generated by that call. The total work performed by the algorithm can be understood as the sum of the work done at each level of this tree. In many Divide and Conquer algorithms, such as binary search or fast exponentiation, the amount of work per level remains bounded, while the depth of the tree grows logarithmically.

The visualization below illustrates how a Divide and Conquer recursion splits the problem and how the work is distributed across levels.

Divide and Conquer is not limited to numerical problems. It also appears naturally when constructing or transforming recursive data structures. Examples include:

• converting a sorted linked list into a balanced binary search tree
• constructing a quad tree from a grid
• building a binary tree by recursively selecting a root and partitioning the remaining elements

In these cases, the input is divided into independent regions or substructures, each of which is processed recursively. The resulting trees are often balanced by construction, and their height is logarithmic with respect to the input size.

What these problems have in common is that the recursive decomposition mirrors the shape of the output data structure. The algorithm does not merely compute a value; it constructs a recursive object by assembling recursively computed parts. Divide and Conquer therefore serves as a bridge between recursion as a control-flow mechanism and recursion as a tool for building complex structured data.

Recursive Descent and Nested Structures

So far, we have seen recursion applied to problems where each recursive step reduces the input in a clear and predictable way: smaller arrays, smaller ranges, smaller numbers. However, recursion truly shines when dealing with nested or hierarchical structures, where the shape of the data is not known in advance. In these cases, recursion is not just a convenient choice, it is often the most natural and readable way to express the solution.

Many data formats and structures are inherently recursive:

• nested strings
• abstract syntax trees
• file systems
• JSON documents
• markup languages

The key observation is that each element may contain other elements of the same kind. This self-similarity makes recursion a perfect fit. Instead of iterating over a flat sequence, the algorithm descends into the structure, processing one level at a time, until it reaches the simplest possible element. Consider a string encoding rule like the following:

• "3[a]2[bc]" → "aaabcbc"
• "3[a2[c]]" → "accaccacc"

The structure of the input is nested, and the depth of nesting is not known beforehand. Any attempt to solve this with loops alone quickly becomes complex and error-prone. A recursive solution, instead, mirrors the structure of the input itself.

function decodeString(s: string): string {
  let index = 0;

  function decode(): string {
    let result = "";
    let num = 0;

    while (index < s.length) {
      const char = s[index];

      if (char >= "0" && char <= "9") {
        num = num * 10 + Number(char);
        index++;
      } else if (char === "[") {
        index++; // skip '['
        const decoded = decode();
        result += decoded.repeat(num);
        num = 0;
      } else if (char === "]") {
        index++; // skip ']'
        return result;
      } else {
        result += char;
        index++;
      }
    }

    return result;
  }

  return decode();
}

This function uses recursion to process the string from left to right, descending into each nested level when encountering a [ and returning when a ] is found. What makes this approach powerful is that:

• each recursive call is responsible for decoding one level of nesting
• the base case is implicit: encountering a closing bracket
• the call stack naturally keeps track of where we are in the string

The recursion depth corresponds exactly to the nesting depth of the input. This tight correspondence between data structure and call stack is a recurring theme in recursive algorithms. To better understand how recursive descent works, it helps to visualize the flow of recursive calls as the algorithm enters and exits nested levels.

The pattern above is a simplified form of recursive descent parsing, a technique widely used in compilers and interpreters. While the example here is intentionally minimal, the same idea scales to much more complex grammars. The important takeaway is not the specific problem, but the mental model:

• recursion follows the structure of the input
• each call handles one level of abstraction
• returning from a call corresponds to finishing a nested construct

At this point, recursion stops being just a way to replace loops. It becomes a tool for understanding and navigating complex structures.

Recursion: Mental Models

At this point, we have seen recursion applied in several different contexts: linear problems, recursive data structures, divide & conquer strategies, and nested representations. Rather than thinking of recursion as a language feature or a clever trick, it is more useful to frame it as a mental model for structuring computation. This section distills the key ideas that recur across all recursive solutions.

The Call Stack as a Data Structure

Every recursive function call is stored on the call stack. Each stack frame contains:

• the function’s local variables
• its parameters
• the point to resume execution after the recursive call returns

Conceptually, the call stack behaves like a standard stack data structure:

• recursive calls push frames
• returning from a function pops frames

This is not an implementation detail to ignore, it is the core mechanism that makes recursion work. Understanding recursion means understanding how the stack grows during descent and shrinks during ascent.

Base Case and Progress

All correct recursive algorithms share two fundamental properties:

• A base case, a condition under which the function stops calling itself
• Guaranteed progress toward the base case, each recursive call must operate on a strictly smaller or simpler version of the problem

If either of these properties is missing, the recursion will not terminate. Most recursion bugs can be traced back to violating one of these two rules.

Recursion vs Iteration

Any recursive algorithm can be rewritten using iteration and an explicit stack. This is not a limitation of recursion, but rather a reflection of its underlying mechanism.

The choice between recursion and iteration is therefore not about what is possible, but about clarity and alignment with the problem:

• iteration is often preferable for flat, linear processes
• recursion excels when the problem or data is naturally hierarchical or self-similar

Recursion trades explicit control flow for a declarative structure that mirrors the problem definition.

Tail Recursion

A recursive function is tail recursive if the recursive call is the last operation performed before returning. In theory, tail recursion can be optimized to reuse stack frames and behave like a loop. In practice, JavaScript and TypeScript engines do not reliably perform tail-call optimization. For this reason, tail recursion should be seen primarily as a conceptual tool rather than a performance guarantee in these environments (even if implemented in other languages, especially in functional programming framreworks).

When Not to Use Recursion

Recursion is not always the right choice. Situations where it may be inappropriate include:

• extremely deep recursion that risks stack overflow
• performance-critical paths where allocation of stack frames is significant
• problems where the recursive structure obscures, rather than clarifies, the logic

Choosing recursion should be a deliberate design decision, not a default.

Recursion as a Modeling Tool

The strongest argument for recursion is not elegance or brevity, but expressiveness. When a problem is recursive in nature, a recursive solution often reads like a direct translation of the problem statement into code. At its best, recursion allows us to reason locally:

• “If the smaller problem is solved correctly…”
• “…then this step is correct as well.”

This shift from global reasoning to local reasoning is what makes recursion such a powerful tool, and why it remains a foundational concept in computer science.

Exercises