Assessing Recursion Depth and Choosing Iterative Java Implementations

Good to see you again. In the previous lesson, you selected Java collections by identifying the operation repeated on the algorithm’s critical path. Now apply the same discipline to function calls: recursion may be elegant and still be unsafe if the input can force too many calls to remain active at once.

By the end of this lesson, you should be able to estimate a recursive algorithm’s maximum depth, state its auxiliary stack space, and replace recursion with an iterative Java implementation when the depth is not safely bounded. This will matter frequently in tree, graph, grid, and backtracking problems.

---

The memory hidden in a recursive call

Every active Java method call occupies a stack frame on the current thread’s call stack. A frame holds the information required to pause and later resume that call: parameters, local variables, return location, and runtime bookkeeping.

Consider recursive traversal of a singly linked list:

static int sumRecursive(ListNode node) {
    if (node == null) {
        return 0;
    }

    return node.val + sumRecursive(node.next);
}

If the list contains $n$ nodes, sumRecursive(head) calls itself once per node before it can begin returning. At the deepest moment, the stack contains calls for every node on the chain.

The important measurement is not the total number of calls made over the entire execution. It is the maximum number of calls that are alive simultaneously.

• Total calls: how much work the program did.
• Recursion depth: the largest number of simultaneously active calls.
• Auxiliary stack space: memory used by those active calls, excluding the input itself and usually excluding required output storage.

If each call has only a constant amount of local state, a recursion depth of $D$ uses $O(D)$ auxiliary stack space.

A StackOverflowError can arise in two fundamentally different ways:

1. The recursion is incorrect. There is no base case, or recursive calls do not move toward it.
2. The recursion is correct but too deep. A valid input forms a long chain, such as a skewed tree, a line graph, or a large connected grid region.

The second case is especially relevant in interviews. A recursive solution can be logically correct, have optimal time complexity, and still fail on a hidden test because the input shape drives depth to $O(n)$.

Watch this short visualization from “Coding Interview Fundamentals: Depth-First Search and Recursion (Binary Trees)” by Hello Interview. It makes the connection between recursive calls, DFS backtracking, and the active stack frames concrete.

For a recursive binary-tree algorithm, the active calls correspond to one root-to-leaf path, not all nodes in the tree at once. Therefore its stack usage is usually $O(h)$, where $h$ is the tree height.

---

Estimate depth from structure, not just input size

A problem statement may say “there are $n$ nodes,” but that alone does not tell you whether recursion is safe. You must ask what shape the input may take.

Recursive structure	Maximum depth	Auxiliary call-stack space	Practical implication
factorial(n) or linked-list recursion	$n$	$O(n)$	Risky for large $n$
Binary search	$O(\log n)$	$O(\log n)$	Typically safe
Balanced binary tree	$O(\log n)$	$O(\log n)$	Usually safe
Arbitrary binary tree	$O(n)$ worst case	$O(n)$ worst case	Must account for a skewed tree
Recursive DFS in a graph	$O(V)$ worst case	$O(V)$ worst case	A line graph can force one call per vertex
Recursive flood fill on an $M$ by $N$ grid	$O(MN)$ worst case	$O(MN)$ worst case	Prefer iteration for large grids

For a perfect binary tree with $n$ nodes, height is approximately:

$$\lfloor {\log }_{2}n\rfloor +1$$

A tree with $100,000$ nodes can therefore have a height near $17$ if balanced. But if each node has only a left child, its height is $100,000$. Recursive traversal has the same $O(n)$ time in both cases, but radically different stack behavior.

This distinction also prevents a common analysis error:

An algorithm can make an enormous number of calls over time without having an enormous call stack.

Naive recursive Fibonacci, for example, has exponential time because it recomputes subproblems, but its maximum recursion depth is only $O(n)$. It computes the left branch fully, returns, then computes the right branch; the two branches are not simultaneously active.

Similarly, do not assume $O(D)$ stack space if each frame allocates nonconstant extra memory. For example, allocating a new array proportional to the remaining input in every recursive call adds much more than the call frames themselves. State clearly what you are counting:

• Recursive frames: $O(D)$, assuming constant-sized local state.
• A visited array or set: often $O(V)$ additional auxiliary space.
• A returned result list: normally report separately if it is required output.

Read the opening and iterative-DFS sections of DevWeekends’ “Depth-First Search (DFS)” for a concise treatment of depth as the central space variable and the reason an explicit stack avoids dependence on the language call stack.

Java-specific judgment

Java does not promise a portable “safe recursion depth.” Available stack space depends on the JVM configuration, operating system, thread settings, and the size of each method’s frame. Changing JVM stack settings is not an interview solution; you cannot assume the evaluator will run with your chosen configuration.

Also, Java does not guarantee tail-call optimization. Even if a recursive call is syntactically the final action of a method, write an iterative version when depth can grow linearly with a large input.

A useful interview rule is:

If the input constraints permit a depth proportional to a large $n$, use an explicit ArrayDeque unless the problem explicitly guarantees shallow depth.

---

Move the stack from the JVM to your code

An iterative version does not make the traversal “stack-free.” It replaces the implicit, fixed-size call stack with an explicit data structure, generally an ArrayDeque, whose contents live in ordinary heap-managed memory.

For the linked-list sum, recursion is unnecessary because there is no work to resume after returning from node.next:

static int sumIterative(ListNode node) {
    int total = 0;

    while (node != null) {
        total += node.val;
        node = node.next;
    }

    return total;
}

This version has:

• Time: $O(n)$
• Auxiliary space: $O(1)$

It is better than the recursive version in both stack safety and auxiliary space.

For DFS, however, backtracking is essential: after exploring one neighbor, the algorithm must remember where to resume. The explicit stack holds that suspended work.

Here is an iterative DFS for reachability in an adjacency-list graph:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

static List<Integer> dfsIterative(List<Integer>[] graph, int start) {
    boolean[] seen = new boolean[graph.length];
    Deque<Integer> stack = new ArrayDeque<>();
    List<Integer> order = new ArrayList<>();

    stack.push(start);
    seen[start] = true;

    while (!stack.isEmpty()) {
        int node = stack.pop();
        order.add(node);

        List<Integer> neighbors = graph[node];

        for (int i = neighbors.size() - 1; i >= 0; i--) {
            int next = neighbors.get(i);

            if (!seen[next]) {
                seen[next] = true;
                stack.push(next);
            }
        }
    }

    return order;
}

The algorithm has the same reachability and time guarantees as a standard recursive DFS:

$$O(V+E)$$

The space requires more careful reporting:

• seen uses $O(V)$.
• The explicit stack can hold $O(V)$ vertices in the worst case.
• Therefore total auxiliary space is $O(V)$.

The reverse loop is intentional. Since the stack is last-in, first-out, pushing neighbors in reverse adjacency-list order makes the first listed neighbor available first. For a tree, this reproduces ordinary recursive preorder traversal order.

For a general graph, traversal order is often not part of the required result. If an interviewer requires behavior that precisely mirrors recursive DFS, especially for parent relationships, postorder processing, or backtracking state, a stack entry must store more than just a node.

The key conversion principle is:

A recursive frame stores the current state plus a continuation: what remains to do after the recursive call returns. An iterative stack must store the same information explicitly.

---

When a node stack is not enough

A preorder traversal only needs to remember pending nodes. Inorder traversal is more demanding: after exploring a node’s left subtree, you must return to that node, process it, and then enter its right subtree.

The recursive version is concise:

static void inorderRecursive(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }

    inorderRecursive(node.left, result);
    result.add(node.val);
    inorderRecursive(node.right, result);
}

The iterative version makes the paused recursive calls visible:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

static List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        result.add(current.val);

        current = current.right;
    }

    return result;
}

The inner loop descends left while pushing every ancestor whose processing has been postponed. Popping means that ancestor’s left subtree is complete, so it is now time to visit the node and move to its right subtree.

For a tree of height $h$:

$$\text{auxiliary space}=O(h)$$

Thus a balanced tree uses $O(\log n)$ stack space, while a fully skewed tree uses $O(n)$. The asymptotic space is unchanged from recursion, but the iterative implementation avoids exhausting Java’s call stack on deep inputs.

Watch “L10. iterative Inorder Traversal in Binary Tree” by take U forward for a visual simulation of this conversion.

For interview implementation, prefer:

Deque<TreeNode> stack = new ArrayDeque<>();

rather than the legacy Stack class. ArrayDeque supplies the stack operations you need:

stack.push(node);
TreeNode node = stack.pop();
TreeNode top = stack.peek();

---

A fast recursion-safety checklist

Before committing to recursion, make this assessment:

1. Identify the longest possible call chain.
   For a tree, this is height; for a graph or grid DFS, it is the longest path the search can follow; for a shrinking numeric problem, it is the number of reductions before the base case.

2. Use the worst legal input shape.
   “Binary tree” does not imply balanced. “Grid” does not imply a small connected component. “Graph” can contain a path through every vertex.

3. State stack space from maximum simultaneous calls.
   With constant local work per call, depth $D$ gives $O(D)$ call-stack space.

4. Account for other auxiliary structures separately.
   A boolean[] seen, HashSet, explicit stack, path list, or memo table may dominate the recursive frames.

5. Choose iteration when depth is unbounded or linear in a large input.
   Use ArrayDeque and explicitly represent the paused state that recursion previously stored for you.

A concise interview explanation might sound like this:

“The traversal is $O(V+E)$. Recursive DFS can reach depth $O(V)$ on a line-shaped graph, which is unsafe for large inputs in Java. I’ll use an ArrayDeque as an explicit stack and a visited array, so the algorithm remains $O(V+E)$ time and $O(V)$ auxiliary space without relying on the call stack.”

---

Key takeaways

• Recursion depth is the maximum number of active calls, not the total number of calls.
• With constant work per frame, recursive auxiliary stack usage is $O(D)$, where $D$ is maximum depth.
• Balanced trees and binary search usually have logarithmic depth; linked lists, skewed trees, line graphs, and large flood fills can have linear depth.
• Java offers no portable safe recursion limit and does not guarantee tail-call optimization.
• Iteration moves suspended computation from the JVM call stack into an explicit ArrayDeque; it improves stack safety but does not automatically reduce asymptotic auxiliary space.
• When converting recursion, preserve each frame’s essential information: current node, pending work, and—in more complex traversals—the next child or phase to process.

Next, you will analyze loops with multiple pointers. Rather than multiplying loop bounds mechanically, you will bound how many times each pointer can move across the entire algorithm.