What does "recursion depth" mean?

AlgorithmsJunior~3 min read

Short answer

Recursion depth is the number of simultaneously active recursive calls (the depth of the call stack) during an algorithm's execution; it is also often used to mean the maximum possible or actual maximum depth of such calls for a given input. Stack consumption (memory) and the risk of a stack overflow depend directly on the recursion depth.

Detailed answer

Definition

Current recursion depth: how many frames of the recursive function are on the stack at once at a given moment of execution.
Maximum recursion depth: the largest value of the current depth over the algorithm's run on a given input. It is often used to estimate memory cost and the solution's reliability.

Why this matters

Stack memory: each recursive call holds local variables and a return address. Stack memory grows proportionally to depth: O(depth).
Stack overflow: if the depth exceeds the runtime/language limit, the program crashes with a stack overflow error.
Asymptotics: recursion depth often equals the problem's natural measure (input size, tree height, log n, etc.) and determines the space complexity.

Code examples

Example 1: factorial with maximum-depth measurement in JavaScript.

function fact(n, depth = 1, stats = { maxDepth: 0 }) {
  stats.maxDepth = Math.max(stats.maxDepth, depth);
  if (n <= 1) return 1;
  return n * fact(n - 1, depth + 1, stats);
}

const stats = { maxDepth: 0 };
console.log(fact(5, 1, stats)); // 120
console.log('maxDepth =', stats.maxDepth); // 5
// The maximum depth for fact(n) equals n (linear recursion).

Example 2: computing the height (maximum depth) of an N-ary tree in Python - the recursion depth equals the tree height.

class Node:
    def __init__(self, val, children=None):
        self.val = val
        self.children = children or []

def max_depth(root, depth=1):
    if root is None:
        return 0
    if not root.children:
        return depth
    return max(max_depth(c, depth + 1) for c in root.children)

root = Node(1, [Node(2), Node(3, [Node(4)])])
print(max_depth(root))  # 3
# The recursion depth when traversing a tree equals the tree height.

Estimating recursion depth for typical problems

Linear recursion (factorial, summing 1..n): depth = n → O(n).
Binary search: depth ≈ ⌊log2 n⌋ → O(log n).
Tree traversal (DFS): depth = tree height h → O(h). For an unbalanced tree h can be O(n).
Quicksort: average depth = O(log n), worst case = O(n) (with a poor pivot choice).

Recursion depth and space complexity

The space complexity of a recursive algorithm is usually O(depth), because that many call frames are on the stack at once. Approximate memory consumption can be estimated as: memory ≈ frame_size × depth.

Frame size includes local variables, parameters, the return address, and runtime bookkeeping.
With tail-call optimization, tail recursion can keep the stack at O(1), because the frame is reused.

Tail recursion and optimization

A tail call is a recursive call that is the last operation performed by a function. With tail-call optimization (TCO) support, the recursion depth can logically be large, but the stack physically stays at O(1). However, in many popular environments TCO is either unavailable or not guaranteed.

A reliable approach for deep recursion: rewrite it as an iterative algorithm with an explicit stack/loop.

Comparison of a tail-recursive and an iterative version, using the sum of 1..n in JavaScript.

function sumRange(n, acc = 0) {
  if (n === 0) return acc; // tail call
  return sumRange(n - 1, acc + n);
}

// Iteratively (more reliable for large n):
function sumRangeIter(n) {
  let acc = 0;
  while (n > 0) {
    acc += n;
    n--;
  }
  return acc;
}

console.log(sumRange(5));     // 15
console.log(sumRangeIter(5)); // 15

Limitations and practical advice

Control the base case. It must be guaranteed to trigger and reduce the depth; otherwise infinite recursion is possible.
Estimate the worst-case depth on real data: for unbalanced structures it can be linear.
Configuration/limits: some environments let you change the recursion limit or stack size (for example, in some languages/runtimes), others do not; account for the target platform's constraints.
For potentially large depth, use iterative solutions or your own stack/queue.
Do not rely on TCO where it is not guaranteed; plan for O(depth) memory.

How to answer in an interview

Give the definition: recursion depth is the number of active recursive calls and/or the maximum depth reached.
Mention the connection to the stack and the O(depth) space complexity.
Give an example (factorial/DFS) and say what the depth depends on (n, tree height, log n).
Describe the risk of stack overflow and the alternatives (iteration, a custom stack, balancing, tail recursion).

Short Answer

Interview ready

Premium

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