What Is Recursion? A Function That Calls Itself

Recursion is solving a problem by having a function call itself on a smaller version of the problem, until it reaches a simple base case it can answer directly.

Recursion expresses a problem in terms of itself. A recursive function handles a tiny base case directly and reduces every larger case toward that base by calling itself on smaller input. It is elegant for naturally nested data like trees and file systems, but each call consumes stack space, so unbounded recursion can overflow the stack.

The two parts of recursion

Every correct recursive function needs a base case (a condition that stops the recursion and returns a direct answer) and a recursive case (which reduces the problem and calls itself). Miss the base case, or fail to make progress toward it, and the recursion never ends.

When recursion shines

Tree and graph traversal, where structure is naturally nested.
Divide-and-conquer algorithms like quicksort and mergesort.
Walking hierarchical data such as directories or the DOM.
Problems defined recursively, like factorials or Fibonacci numbers.

Recursion vs iteration

Anything recursive can be written with a loop, and vice versa. Recursion is often clearer for nested structures but uses stack space per call. Iteration uses constant stack space and is safer for very deep problems, at some cost in readability.

The stack cost

Each recursive call pushes a stack frame. Deep recursion can exhaust the limited call stack and cause a stack overflow. Some languages optimize tail calls to avoid this, but many do not, so deep recursion is risky.

A quick example

A factorial is factorial(n) = n <= 1 ? 1 : n * factorial(n - 1). The base case (n <= 1) stops the recursion; each call shrinks n toward it.

Recursion in CI

A recursion bug (a missing or unreachable base case) shows up as a stack overflow that fails every run identically, so retrying never helps. Latchkey distinguishes deterministic crashes from transient infrastructure failures, retrying only the latter so a real recursion bug stays visible.

Key takeaways

Recursion solves a problem by calling itself on smaller inputs until a base case.
It needs a reachable base case and real progress, or it never terminates.
Deep recursion can overflow the stack; that is a deterministic bug, not a flake.