DFS: Finish Times, Recursion vs an Explicit Stack, and What a Cycle Looks Like

A package resolver walks dependsOn with a recursive method. The chain is 8,000 modules and acyclic. The process dies with StackOverflowError on a graph that would have been an 8,000-slot deque. Ops raises -Xss. The next weekly build “succeeds”: a cycle core-utils → app-api → core-utils hits a seen set, the edge is skipped, and the planner emits an order anyway. Install deadlocks on startup. Nobody “forgot a graph library.” They used JVM call frames as the walk, and they treated started as finished.

DFS walks as deep as the edges allow, then stamps a finish time on the way out — recursion and an explicit stack are the same walk. A back edge into a vertex that has started but not finished is a cycle. The seen set that only means “don’t explode” will hide that edge.

This post is that walk: finish times, recursion versus ArrayDeque, and a back edge as the shape of a cycle. Families and Big-O language live on the Algorithms Roadmap. The layout — adjacency list versus matrix — lives on Graphs. Full directed versus undirected cycle procedures live on Cycle Detection. This is not a shortest-path tutorial, and not a reason to recurse over a production call graph without a finish stamp.

Go deep, then stamp a finish time

From a start vertex u you mark u started, walk each unused neighbor as far as the edges allow, and only then record that u is finished. The interesting number is the finish time: a clock that ticks when you leave, after every descendant in this walk has left. A queue of a frontier is a different procedure.

Start. If u is unseen, mark it started. The walk is now inside u.
Descend. For each neighbor v in list order: if v is unseen, run the same procedure on v. If v is started and not finished, the edge u → v is a back edge — do not pretend the graph is a DAG.
Finish. After every neighbor is handled, stamp finish(u) and leave.

A forest is the same procedure in a loop: for each vertex, including those with an empty out-list, start a walk if it is still unseen. Neighbor order is the adjacency-list order; different lists yield different numbers. On a DAG, one fact stays: a vertex finishes after every vertex it can reach in this walk. Reverse finish order is the tease for topological sort; that post owns the job.

Note: “Started” and “finished” are not the same bit. Collapsing them into one seen set is how the resolver emitted an order on a cyclic graph.

A walked pass: finish times on a DAG

Four vertices. Directed edges A → B, A → C, B → D, C → D. Clock ticks only on leave — the number this post owns.

        A
       / \
      B   C
       \ /
        D

dfs(A)
  start A
  neighbor B:
    start B
    neighbor D:
      start D
      finish D @1
    finish B @2
  neighbor C:
    start C
    neighbor D: already finished — skip
    finish C @3
  finish A @4

finish times:  D=1  B=2  C=3  A=4
finish order:  D, B, C, A

Each edge is examined once. C → D lands on a finished vertex — not a cycle. Reverse finish order A, C, B, D is a valid “run A before anything A can reach.” Do not implement Kahn’s algorithm here; take that to Topological Sort. If a vertex is missing from g.keySet() because you only stored tails, it never gets a walk — add both ends when you insert an edge.

Recursion vs an explicit stack

The recursive procedure is a stack: each call frame is a vertex you have started and not finished. Leaving u is a return. That is why the 8,000-deep chain died. Default JVM stack is not |V| frames. -Xss is a bigger call stack, not an algorithm.

The same walk sits on an explicit stack: Deque plus ArrayDeque, push / pop at one end. You still mark started on entry. You still stamp finish after neighbors. A deque does not return for you — push a leaving marker so the finish stamp happens when that vertex comes back to the top.

iterative, same DAG; push LEAVE under the children (neighbors reversed):

push ENTER(A)
pop ENTER(A)  start A   push LEAVE(A), ENTER(C), ENTER(B)
pop ENTER(B)  start B   push LEAVE(B), ENTER(D)
pop ENTER(D)  start D   push LEAVE(D)
pop LEAVE(D)  finish D @1
pop LEAVE(B)  finish B @2
pop ENTER(C)  start C   D already started — do not push D
pop LEAVE(C)  finish C @3
pop LEAVE(A)  finish A @4

Same finish times as recursion when you restore left-to-right neighbor order via LIFO. Skip the LEAVE marker and finish on first pop, and you stamp A before D — a preorder dump, not a finish time. Do not use java.util.Stack; the stack post already called that type a synchronized Vector. ArrayDeque is the layout.

What a cycle looks like

Keep the walk. Add edge C → B.

A → B → C
    ↑   |
    +---+          C → B  (back edge)

dfs(A)
  start A
  dfs(B)
    start B
    dfs(C)
      start C
      neighbor B: started, not finished  ← back edge C → B

B is still on the stack (call frames or ArrayDeque). The walk has not left B. An edge into that open vertex closes a directed cycle. An edge into a finished vertex does not — that was C → D on the DAG.

That is the shape, not the full directed-versus-undirected procedure (colors as a teaching palette, the parent trick so an undirected edge you just arrived on is not a cycle). Those live on Cycle Detection. If you only needed “does this dependency graph have a loop?”, you still start with this walk; you do not stop at a boolean seen.

Note: On an undirected graph the edge back to the parent looks like a back edge if you only test “started and not finished.” Do not patch that here with a parent pointer. Read the cycle post.

Java sketch

Fields: adjacency list g, started, finish, a clock. The else if is the shape from the last section, not a complete detector.

void forest() {
    for (String u : g.keySet()) {
        if (!started.contains(u)) {
            recursive(u);
        }
    }
}

void recursive(String u) {
    started.add(u);
    for (String v : g.getOrDefault(u, List.of())) {
        if (!started.contains(v)) {
            recursive(v);
        } else if (!finish.containsKey(v)) {
            // back edge u → v: v is open (started, not finished)
        }
    }
    finish.put(u, clock++);
}

The same walk with an explicit stack. leaving is the marker that preserves finish-after-neighbors. Push unseen neighbors in reverse so the first list entry is popped first.

record Frame(String v, boolean leaving) {}

void iterative(String start) {
    Deque<Frame> stack = new ArrayDeque<>();
    stack.push(new Frame(start, false));
    while (!stack.isEmpty()) {
        Frame f = stack.pop();
        if (f.leaving()) {
            finish.put(f.v(), clock++);
            continue;
        }
        if (!started.add(f.v())) {
            continue;
        }
        stack.push(new Frame(f.v(), true));
        List<String> nbrs = g.getOrDefault(f.v(), List.of());
        for (int i = nbrs.size() - 1; i >= 0; i--) {
            String w = nbrs.get(i);
            if (!started.contains(w)) {
                stack.push(new Frame(w, false));
            }
        }
    }
}

started.add on enter guards a vertex pushed more than once before its first enter runs. Do not stamp finish in that continue branch. For a forest, loop iterative(u) for each unseen u. Do not replace the deque with a Queue and keep the DFS name.

Note: Recursion is fine for a lecture graph of twenty nodes. Production module graphs want the deque. A shared started set without a lock is not a parallel DFS.

Complexity

Let V be vertices and E edges. The layout is an adjacency list — neighbor iteration is the hot path; the graph post already picked that for sparse networks.


Time	Θ(V + E): each vertex entered once, each edge examined once
Extra RAM	`started` + `finish`, O(V), plus the stack
Stack	O(V) on the longest path; recursion spends that in JVM frames

You are iterating a layout, not ranking keys — the hub’s n log n comparison story does not apply. A dense matrix makes neighbor scans Θ(V²); that is the layout, not DFS. Space that kills the resolver is the call stack. An ArrayDeque of Frame objects is still O(V) and sits on the heap.

When not to reach for DFS

Skip this walk when:

Unweighted shortest path / level order. That frontier is a queue. A stack visits in a different order and returns the wrong hop count. Do not re-derive BFS here.
A total order on a DAG. Finish times are an input to that procedure. Kahn and “sort by DFS finish” live on the topological-sort post.
Weighted shortest path. Later catalog: Dijkstra, Bellman-Ford. Finish times do not rank edge weights.

Do not recurse over a production-sized graph and hope the default stack holds. Do not ship -Xss as the fix for depth. Do not treat one seen set as cycle detection. “Is there an edge u → v?” is the graph’s hasEdge, not a search from u.

JDK: no `Dfs` class

There is no java.util.Dfs. Layout is Map<K, List<K>> (Graphs). The explicit stack is Deque<Frame> stack = new ArrayDeque<>() (Stack). Recursion is a method plus started and finish.

Prefer the explicit ArrayDeque when |V| can be large. Prefer recursion when the graph is tiny and the lecture is the finish-time invariant. Do not synchronize with java.util.Stack. Do not copy Files.walk and call it DFS of a service graph — that API walks a file tree.

Cheat sheet

Job:         walk deep, stamp finish times; see a cycle as a back edge
Start:       mark u started; the walk is now inside u
Descend:     unseen neighbor → DFS it
Finish:      after neighbors, stamp finish(u) and leave
Cycle shape: edge to a vertex that is started and not finished
Forest:      loop all vertices; start a walk on each unseen one
Recursion:   call frames are the stack; depth can be |V|
Explicit:    ArrayDeque + LEAVE marker so finish stays after neighbors
Time:        Θ(V + E) on an adjacency list
JDK:         no Dfs type; Map+List, HashSet, ArrayDeque
Do not:      one seen bit; -Xss as the algorithm; Stack; call this BFS

Do:

Keep started and finished as two facts. Stamp finish only on the way out.
Use ArrayDeque when the longest path can approach |V|.
Treat a back edge to an open vertex as a cycle, then read the cycle-detection post for directed vs undirected.

Don’t:

Recurse on a production graph and raise -Xss when it dies.
Collapse started into a single seen set and emit an order on a cyclic DAG.
Push vertices without a leaving marker and call the pop time a finish time.
Swap a queue for a stack and claim unweighted shortest path.

Wrap-up

DFS is go-deep, then stamp a finish time. Recursion makes the stack invisible until the JVM runs out of frames. An ArrayDeque with a leaving marker is the same walk on the heap. A back edge into a vertex that has started but not finished is what a directed cycle looks like; the full detection procedures are a different post. Reverse those finish times when you need to order a DAG — that is the next procedure, not a second DFS.

Next optional step in the series Order a DAG before you run the work — Kahn and DFS finish times. Topological Sort: Order a DAG Before You Run the Work

DFS:Finish Times, Recursion vs an Explicit Stack, and What a Cycle Looks Like

Go deep, then stamp a finish time

A walked pass: finish times on a DAG

Recursion vs an explicit stack

What a cycle looks like

Java sketch

Complexity

When not to reach for DFS

JDK: no `Dfs` class

Cheat sheet

Wrap-up

Reservoir Sampling:One Pass When You Do Not Know n Up Front

Binary Exponentiation:pow(base, exp) in Logarithmic Multiplies

Fisher-Yates:Shuffle in Place Without Bias

Euclid GCD:Subtract, Then Mod, Then Extended Coefficients

Go deep, then stamp a finish time

A walked pass: finish times on a DAG

Recursion vs an explicit stack

What a cycle looks like

Java sketch

Complexity

When not to reach for DFS

JDK: no Dfs class

Cheat sheet

Wrap-up

Related posts

Reservoir Sampling:One Pass When You Do Not Know n Up Front

Binary Exponentiation:pow(base, exp) in Logarithmic Multiplies

Fisher-Yates:Shuffle in Place Without Bias

Euclid GCD:Subtract, Then Mod, Then Extended Coefficients

JDK: no `Dfs` class