Turning Recursion Into Iteration

Recursion uses the call stack. An iterative version uses a stack you control. The logic is identical; the difference is that your stack lives on the heap and does not overflow at ten thousand frames.

When you are forced to

• Depth grows with input size and the input can be large.
• You are processing user data of unknown shape - a deeply nested JSON payload will crash a recursive walk.
• You need to pause, resume or cancel partway through.

The simple case: no combining

When the recursion just visits things and does not combine results, the conversion is mechanical - push instead of call.

// Recursive.
function walk(node, visit) {
  if (!node) return
  visit(node.value)
  walk(node.left, visit)
  walk(node.right, visit)
}

// Iterative — an explicit stack, no depth limit.
function walkIterative(root, visit) {
  if (!root) return

  const stack = [root]

  while (stack.length) {
    const node = stack.pop()
    visit(node.value)

    // Right first, so left comes off the stack first.
    if (node.right) stack.push(node.right)
    if (node.left) stack.push(node.left)
  }
}

const demoTree = { value: 1, left: { value: 2, left: null, right: null }, right: { value: 3, left: null, right: null } }
walk(demoTree, (v) => console.log("recursive", v))
walkIterative(demoTree, (v) => console.log("iterative", v))

Pushing right before left looks backwards and is not. A stack reverses order, so the last one pushed is the first one visited.

The accumulating case

When each call needs its children's results, carry the accumulator in the stack rather than in the return value.

function maxDepth(root) {
  if (!root) return 0

  let best = 0
  const stack = [{ node: root, depth: 1 }]

  while (stack.length) {
    const { node, depth } = stack.pop()
    best = Math.max(best, depth)

    if (node.left) stack.push({ node: node.left, depth: depth + 1 })
    if (node.right) stack.push({ node: node.right, depth: depth + 1 })
  }

  return best
}

const demoTree = { value: 1, left: { value: 2, left: { value: 4, left: null, right: null }, right: null }, right: null }
console.log(maxDepth(demoTree))  // 3

Tail recursion, and why it does not help here

A tail call is a recursive call that is the very last thing a function does - nothing waits on its result. Some languages reuse the stack frame for these, making them free.

JavaScript specified this and then almost nobody implemented it. Safari does; V8 and SpiderMonkey do not. So writing your recursion in tail form is good style and buys you nothing in Chrome or Firefox. Convert to a loop instead.

The honest advice

Write it recursively first. It is easier to get right, and easier to check. Convert only when the depth is genuinely a risk - most trees are shallow, and an unnecessary explicit stack is just harder code.