Recursion
Recursion is a technique where a function solves a problem by calling itself with a simpler version of the input, repeating until it reaches a base case that can be answered directly. The results from smaller calls are then combined to produce the answer for the original input.
▶Architecture Diagram
🔄 ProcessDashed line animations indicate the flow direction of data or requests
Some problems do not decompose cleanly into a fixed sequence of steps. When the input is a tree, when the depth is unknown, or when the problem is defined in terms of itself -- such as 'the factorial of n is n times the factorial of n minus one' -- a loop requires explicit stack management with indices or queues. That bookkeeping often obscures the structure of the problem. Recursion lets you express the solution in the same terms the problem is defined, without manually tracking traversal state.
Recursion is central to functional programming because it replaces mutable loop variables with function arguments, preserving the style of computing through value transformation rather than state mutation. Languages like Lisp, Haskell, and Erlang rely on recursion as the primary looping mechanism. Even in languages with loops, recursive solutions remain valuable for problems whose structure is inherently self-similar.
A recursive function always has at least one base case and at least one recursive case. The base case detects the simplest possible input and returns a value directly. The recursive case makes progress toward the base case by passing a smaller or simpler version of the input to the same function, then combining that result with any additional work at the current level. Each function call occupies a frame on the call stack; when the base case is reached, frames unwind in reverse order and results propagate back up.
Factorial with a clear base case
function factorial(n: number): number {
if (n === 0) return 1; // base case
return n * factorial(n - 1); // recursive case
}
factorial(5); // 120The base case stops the recursion when n reaches zero. The recursive case reduces the problem by one step each time, so the base case is always eventually reached.
Tree traversal without manual stack management
type TreeNode = {
value: number;
children: TreeNode[];
};
function sumTree(node: TreeNode): number {
if (node.children.length === 0) {
return node.value;
}
const childSum = node.children.reduce(
(acc, child) => acc + sumTree(child),
0
);
return node.value + childSum;
}
The function does not need to know the tree's depth in advance. It delegates summing each subtree to the same function, and the base case handles leaf nodes.
Recursion and iteration are computationally equivalent -- anything expressible with one can be expressed with the other. The choice is about clarity. Recursion wins when the problem structure is self-similar or the depth is not known ahead of time. Iteration wins when the number of steps is fixed and the overhead of function calls matters. Deep recursion on runtimes that do not optimize tail calls can cause stack overflow errors, which is the main practical risk to watch for.
Recursive solutions are often concise and match the shape of the problem, but each call frame adds memory overhead. For shallow or bounded recursion this is negligible. For deep or unbounded recursion -- processing a very large list recursively, for example -- the call stack can grow large enough to cause runtime errors. Tail-call optimization removes this overhead when the recursive call is the final action, but not all runtimes implement it.
The most reliable way to write a recursive function is to define the base case first and make sure it is always reachable. Then write the recursive case assuming the function works correctly on the smaller input -- this is the inductive assumption. In practice, recursion is clearest on trees and nested structures. For flat sequences, map, filter, and reduce are usually more readable. When stack depth is a concern, consider converting to an explicit loop or using tail-recursive style if the runtime supports it.