The Stack Overflow That Shouldn't Have Happened
A cycle detection function crashed on a graph with 12,000 nodes. Not a million. Twelve thousand.
The recursive DFS worked fine in local tests with synthetic graphs of 500-1000 nodes. But the production graph — a dependency tree from a package manager audit — hit Python's recursion limit (RecursionError: maximum recursion depth exceeded) at around 10,000 frames. The fix everyone suggests? Switch to an iterative approach with an explicit stack. But does it actually run faster, or just avoid the crash?
Here's what the benchmarks show when you pit recursive DFS against iterative stack-based cycle detection across graphs from 100 to 50,000 nodes.
Why Cycle Detection Matters in Interviews
Cycle detection is the foundation for:
- Deadlock detection in resource allocation graphs
- Circular dependency resolution in build systems (topological sort fails if cycles exist)
- Infinite loop prevention in state machines
The classic interview question: "Given a directed graph, detect if a cycle exists." Most candidates reach for recursive DFS with a three-color marking scheme (white/gray/black). It works. Until it doesn't.
Recursive DFS: The Obvious Approach
Here's the textbook solution using three states:
- White (0): unvisited
- Gray (1): currently in the recursion stack (visiting)
- Black (2): fully explored
A cycle exists if we encounter a gray node during traversal.
python
import sys
---
*Continue reading the full article on [TildAlice](https://tildalice.io/recursive-dfs-vs-iterative-stack-cycle-detection-benchmark/)*
Top comments (0)