The recursion depth of DFS is the length of the longest path it walks, not something logarithmic, so a graph shaped like a chain of 100,000 vertices wants 100,000 live frames at once. A default JVM or Android thread stack holds roughly tens of thousands of frames, so it dies with StackOverflowError on input that the O(V + E) bound calls trivial. The explicit stack above does the same work with the same shape but keeps the pending vertices on the heap, which is why traversals that run on untrusted input are usually written iteratively.