Converting recursion to iteration

Recursion depth is bounded by the runtime; an explicit stack is bounded only by the heap. When input size can push depth past a few thousand frames, convert.

The mechanical conversion

Every recursive call becomes a push; every return becomes a pop.

// Recursive: O(h) frames, and h can be n for a degenerate tree.
function inorderRecursive(node, out = []) {
  if (!node) return out;
  inorderRecursive(node.left, out);
  out.push(node.value);
  inorderRecursive(node.right, out);
  return out;
}

// Iterative: the same traversal, with the stack under your control.
function inorder(root) {
  const out = [];
  const stack = [];
  let node = root;

  while (node || stack.length) {
    while (node) { stack.push(node); node = node.left; }   // go left as far as possible
    node = stack.pop();
    out.push(node.value);
    node = node.right;
  }

  return out;
}

Both are O(n) time and O(h) space. Only the second survives a million-node linked-list-shaped tree.

Tail recursion

If the recursive call is the very last action, no state needs preserving and the call becomes a loop:

// Tail recursive — but JavaScript engines will still stack these frames.
const sumTail = (a, i = 0, acc = 0) => (i === a.length ? acc : sumTail(a, i + 1, acc + a[i]));

// The loop that tail-call optimisation would have produced.
const sumLoop = (a) => { let acc = 0; for (const x of a) acc += x; return acc; };

Scheme, Scala and Lua eliminate tail calls; V8 does not, despite it being in the spec. Write the loop.

When not to convert

Tree and graph recursion with branching reads far better recursively, and depth is O(log n) for balanced structures. Converting a clean 6-line DFS into a 25-line stack machine trades a real risk for a real cost — do it when depth is genuinely unbounded, such as recursing over user-supplied nested data.

The middle ground

For deeply nested but linear structures — a long linked list, a deeply chained JSON path — you can often iterate the linear part and recurse only on the branching part. That keeps depth logarithmic while keeping the code readable.