Introduction

Sometimes it is perfectly fine for recursion depth to grow linearly with input size. Sometimes it is a production bug waiting to happen. The correct answer depends on the maximum input, the runtime stack size, and whether you control the shape of the data.

So the question is not whether O(n) stack depth is elegant. The question is whether the worst-case call depth is safely bounded for the environment that will run the code.

When Linear Stack Depth Is Acceptable

If n is small and tightly bounded, linear stack usage can be a reasonable engineering choice. For example, recursively walking a syntax tree with at most a few hundred levels is often fine.

It can also be acceptable when:

• the runtime guarantees enough stack space
• the input is validated before recursion begins
• the recursive version is substantially simpler and less error-prone

In other words, O(n) stack depth is not automatically bad. It is bad when n can become large enough to exhaust the call stack.

Why It Becomes Risky

Each recursive call creates a stack frame containing local variables, return information, and bookkeeping. If the depth grows linearly and the input size is user-controlled, a carefully chosen input can trigger stack overflow.

A classic example is a skewed tree. A recursive depth-first traversal of a balanced tree has depth O(log n), but the same algorithm on a degenerate tree can reach depth O(n).

1class Node:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7
8def recursive_count(node):
9    if node is None:
10        return 0
11    return 1 + recursive_count(node.left) + recursive_count(node.right)

This function is fine for moderate trees. It becomes dangerous if the tree is effectively a long linked list.

Iterative Alternatives

When the worst-case input can be large, convert the algorithm to an explicit heap or stack structure in the heap memory area rather than the call stack. That does not change asymptotic memory usage, but it avoids crashing due to limited stack depth.

1def iterative_count(root):
2    if root is None:
3        return 0
4
5    count = 0
6    stack = [root]
7
8    while stack:
9        node = stack.pop()
10        count += 1
11
12        if node.left is not None:
13            stack.append(node.left)
14        if node.right is not None:
15            stack.append(node.right)
16
17    return count

This version still uses O(n) auxiliary space in the worst case, but it is usually more robust because heap memory is much larger and easier to monitor than the fixed-size call stack.

Tail Calls Usually Do Not Save You

Some developers assume tail-call optimization will eliminate deep recursion. That assumption is unsafe unless the language and runtime explicitly guarantee it for your code pattern.

Many common production environments do not reliably optimize tail calls in all cases. If the algorithm must handle large n, write the iterative version instead of betting on a runtime optimization.

A Practical Decision Rule

Ask these questions:

• What is the largest possible input in production?
• Can an attacker or untrusted caller influence that size or shape?
• What is the stack limit of the runtime and deployment target?
• Is the recursive version simpler enough to justify the risk?

If you cannot answer those concretely, linear stack depth is usually too risky.

Common Pitfalls

• Looking only at average-case depth and ignoring worst-case structure.
• Assuming recursion depth is harmless because the algorithm is O(n) anyway.
• Depending on tail-call optimization that the runtime does not guarantee.
• Testing only small examples and missing stack overflow on realistic production inputs.
• Using recursion on attacker-controlled inputs such as deeply nested JSON or graph paths.

Summary

• Linear stack depth is acceptable only when the worst-case depth is safely bounded.
• The main risk is stack overflow, not asymptotic elegance.
• Recursive code can be cleaner, but iterative code is often safer for unbounded input.
• Balanced structures may behave well while skewed structures do not.
• Evaluate recursion with real runtime limits, not just big-O notation.