How does recursion affect space complexity?

AlgorithmsJunior~3 min read

Short answer

Recursion increases space complexity because of the extra call stack: each function activation holds memory for local variables and a return address. This is usually O(h), where h is the recursion depth. For linear recursion h=O(n), for binary recursion h equals the height of the recursion tree (often O(log n) in divide-and-conquer algorithms). Without tail-call optimization, memory is not freed until the calls unwind; with TCO, tail recursion can have O(1) stack.

Detailed explanation

How space complexity forms under recursion

The call stack: each recursive call creates a frame with its own local data.
Recursion depth h: the maximum number of simultaneously "alive" calls determines the extra memory O(h).
Additional structures: besides the stack, an algorithm may use arrays/caches, which add to the overall estimate.

A basic example: linear recursion vs. iteration

Factorial: the recursive solution uses O(n) stack, the iterative one uses O(1).

// JavaScript
function factRec(n) {
  if (n <= 1) return 1;      // stack depth: n
  return n * factRec(n - 1); // space complexity from the stack: O(n)
}

function factIter(n) {
  let res = 1;               // O(1) extra memory
  for (let i = 2; i <= n; i++) res *= i;
  return res;
}

Binary recursion: depth vs. number of calls

A naive Fibonacci makes exponentially many calls, but the stack depth stays O(n). Space complexity from the stack is determined by the depth, not by the total number of calls.

// JavaScript
function fib(n) {
  if (n <= 1) return n;      // stack depth: n
  return fib(n - 1) + fib(n - 2); // the number of calls is exponential, but the stack: O(n)
}

Divide and conquer: typical estimates

Quicksort: average recursion depth O(log n) → stack O(log n); worst case - O(n). No additional structures (besides the stack) if sorting in place.
Mergesort (top-down): stack O(log n) by depth, but it needs an extra auxiliary array O(n), which dominates.
Binary search: recursive depth O(log n) → stack O(log n). The iterative version is O(1).

Trees/graphs: DFS recursively and iteratively

A recursive DFS uses a call stack of O(h), where h is the tree height/path length; the iterative variant uses an explicit stack of the same asymptotics, but controlled on the heap.

// JavaScript: DFS over a tree
function dfsRec(node) {
  if (!node) return; // stack: O(h)
  process(node);
  for (const child of node.children) dfsRec(child);
}

function dfsIter(root) {
  const stack = [root];      // explicit stack: O(h)
  while (stack.length) {
    const node = stack.pop();
    if (!node) continue;
    process(node);
    // to match recursion order, add children in reverse order
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
}

Tail recursion and TCO

Without tail-call optimization (TCO), even tail calls accumulate stack → O(n).
With TCO enabled, the compiler reuses a single frame → stack O(1).
TCO support depends on the language/compiler/flags; in many web-development environments (for example, a typical JS runtime) TCO is not guaranteed.

// Tail recursion (theoretically TCO → O(1), otherwise O(n))
function sumRecTail(arr, i = 0, acc = 0) {
  if (i === arr.length) return acc; // tail call
  return sumRecTail(arr, i + 1, acc + arr[i]);
}

// The equivalent iteration - always O(1)
function sumIter(arr) {
  let acc = 0;
  for (let i = 0; i < arr.length; i++) acc += arr[i];
  return acc;
}

Accounting for extra memory (caches, buffers)

If recursion uses memoization or temporary buffers, the total space complexity is the sum: stack O(h) plus memory for the cache/buffer. For example, dynamic programming over an array with memoization gives O(n) memory on top of the stack.

Practical takeaways for an interview

Determine the maximum recursion depth h - it is what drives stack consumption.
Account for auxiliary data structures: they can dominate (as in mergesort).
Compare with iteration: recursion can often be rewritten as a loop with an explicit stack/queue, keeping the same time asymptotics while controlling memory.
Evaluate the worst case: in quicksort the stack can grow to O(n).
Know about TCO, but do not rely on it unless the environment guarantees the optimization.

Summary

Recursion adds a stack cost of O(h) to the space complexity, where h is the maximum depth of recursive calls. In some problems this is O(n), in others O(log n); in the worst cases O(n) and a stack overflow are possible. Iterative versions and optimizations (TCO, tail recursion, explicit structures) help keep memory under control.

Short Answer

Interview ready

Premium

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