DFS in C++ and C#: Recursion Limits, Cycles, Topo Sort

Revised November 2026. This tutorial first appeared in Korean in 2021. We recompiled both examples with Apple clang 21 on an Apple M1 Pro, using -Wall -Wextra and -fsanitize=address,undefined. Both compiled cleanly and matched the original output, but the maze example printed a wrong distance when no path existed, and because it enumerates every path it took 46.65 seconds on an empty 7×7 grid. The diagrams are new, and the measured recursion limits for C++ and C#, cycle detection, topological sort and the recursive-versus-iterative order comparison are additions.

This article is for anyone whose recursive DFS passed every test and then crashed on a large input, and for anyone who rewrote DFS with a stack and watched their expected output change. The short version: a recursive DFS runs out of the default stack somewhere between 100,000 and 175,000 levels deep, and an explicit-stack DFS only reproduces the recursive order if it marks vertices when they are popped and pushes neighbours in reverse.

The breadth-first search article runs BFS on the same graph, and the stack article covers the data structure itself.

Recursive DFS and its visit order

Depth-first search follows one direction as far as it can, then backs up to the most recent vertex that still has an unvisited neighbour. Remembering "where to back up to" is the job of a stack. In a recursive implementation the call stack does that job for you, which is what the 2021 article meant when it said DFS "uses a stack" while showing recursive code.

We use the same graph as the BFS article: 8 vertices, edges 1-2, 1-3, 1-4, 2-5, 3-5, 3-6, 4-7, 5-8, 6-8 and 7-8, neighbours checked in ascending order. BFS visited it in distance order, 1 2 3 4 5 6 7 8. DFS dives instead:

From 2 it goes to 5, then climbs back to 3, and continues 3 → 6 → 8 → 7 → 4 without backing up once: seven levels deep. Vertex 4 is directly connected to the start, yet it is visited last; in BFS it had distance 1. DFS order has nothing to do with distance, so to get a shortest path out of DFS you must try every path. We measure what that costs with the 2021 maze code further down.

Recursion vs an explicit stack: why the order changes

There is more than one way to replace recursion with std::stack, and they do not all produce the same order. We ran four versions on the same graph:

void dfsRec(int v) {
    seen[v] = 1;
    order.push_back(v);
    for (int w : adj[v])
        if (!seen[w]) dfsRec(w);
}

// mark on pop; reverse = push neighbours largest-first so the smallest is on top
void dfsStack(int s, bool reverse) {
    std::stack<int> st;
    st.push(s);
    while (!st.empty()) {
        int v = st.top(); st.pop();
        if (seen[v]) continue;             // already visited via another path
        seen[v] = 1;
        order.push_back(v);
        if (reverse) {
            for (auto it = adj[v].rbegin(); it != adj[v].rend(); ++it)
                if (!seen[*it]) st.push(*it);
        } else {
            for (int w : adj[v]) if (!seen[w]) st.push(w);
        }
    }
}

// BFS code with the queue swapped for a stack (marks on push): NOT a DFS
void stackMarkOnPush(int s) {
    std::stack<int> st;
    st.push(s); seen[s] = 1;
    while (!st.empty()) {
        int v = st.top(); st.pop();
        order.push_back(v);
        for (auto it = adj[v].rbegin(); it != adj[v].rend(); ++it)
            if (!seen[*it]) { seen[*it] = 1; st.push(*it); }
    }
}

Output (built with -Wall -Wextra -fsanitize=address,undefined, no warnings):

recursive                          1 2 5 3 6 8 7 4
stack, push in list order          1 4 7 8 6 3 5 2
stack, push in reverse order       1 2 5 3 6 8 7 4
stack, mark on push (not DFS)      1 2 5 8 6 7 3 4

• Pushing neighbours in list order means the last one pushed, 4, comes out first. That is a valid DFS, just one that prefers the largest neighbour.
• Pushing in reverse puts the smallest neighbour on top and reproduces the recursive order exactly. Use this when you convert recursive code and need identical output, for example to keep existing tests green.
• Taking BFS code and swapping the queue for a stack (marking on push) is not DFS. When the search reaches 6, its neighbour 3 has not been visited, so a real DFS would go there next. Here 3 was already "marked" back when 1 was processed, so it is skipped. No neighbour ordering can produce this sequence. It is harmless for counting connected components, but wrong for anything that depends on when a vertex finishes, such as cycle detection and topological sort.

The rule of thumb: BFS marks on push (measured in the BFS article), iterative DFS marks on pop. Because the same vertex can sit on the stack more than once, the if (seen[v]) continue; right after popping is essential.

Recursion depth limits: where C++ and C# crash

Recursion depth depends on the shape of the graph. The worst case is a path graph, 0-1-2-...-(N-1), where the depth equals N. Linked-list-shaped trees and long single-lane corridors in a maze look exactly like this. We increased N and bisected for the first value that crashes.

// Path graph 0-1-2-...-(N-1): recursive DFS goes N calls deep.
std::vector<std::vector<int>> adj;
std::vector<char> seen;
int visited = 0;

void dfs(int v) {
    seen[v] = 1;
    visited++;
    for (int w : adj[v])
        if (!seen[w]) dfs(w);
}

int main(int argc, char** argv) {
    int n = std::atoi(argv[1]);
    adj.assign(n, {});
    seen.assign(n, 0);
    for (int i = 0; i + 1 < n; i++) { adj[i].push_back(i + 1); adj[i + 1].push_back(i); }
    dfs(0);   // or dfsIter(0): the explicit-stack version from above
    std::printf("visited %d\n", visited);
}

The C# version has the same structure (dotnet new console, net10.0, C# 14, Release build):

int n = int.Parse(args[0]);
var adj = new List<int>[n];
for (int i = 0; i < n; i++) adj[i] = new List<int>(2);
for (int i = 0; i + 1 < n; i++) { adj[i].Add(i + 1); adj[i + 1].Add(i); }
var seen = new bool[n];
int visited = 0;

void Dfs(int v)
{
    seen[v] = true;
    visited++;
    foreach (int w in adj[v])
        if (!seen[w]) Dfs(w);
}

Dfs(0);
Console.WriteLine($"visited {visited}");

On an Apple M1 Pro the macOS main-thread stack is 8,176 KB according to ulimit -s. Results:

The exact boundary moves by a handful depending on the environment: the same C++ -O2 binary reached 174,273 from the shell but 174,264 when launched from Python's subprocess, and the C# boundary shifted by one or two between builds. Remember it as roughly 170k for C++ -O2, 130k for -O0 and 100k for C#. Dividing 8 MB by N, each call costs about 48 bytes at -O2 and about 64 bytes at -O0.

Here is what C# printed for N = 1,000,000:

Stack overflow.
Repeated 104514 times:
--------------------------------
   at Program+<>c__DisplayClass0_0.<<Main>$>g__Dfs|0(Int32)
--------------------------------
   at Program.<Main>$(System.String[])

Two things stand out for C#. First, a StackOverflowException cannot be caught with try/catch; the process is terminated, as the StackOverflowException page on Microsoft Learn states. On a server, one deep request takes the whole process down. Second, with the default tiered compilation a method starts in unoptimized Tier 0 code. A deep recursion reaches the bottom before the optimized version is swapped in, which is the likely reason the default run died at about 100k with larger frames, while DOTNET_TieredCompilation=0 reached the same 174k as C++ -O2. Do not treat that switch as a fix.

The actual fixes, in order of preference: (1) use an explicit stack — the table shows 10 million vertices with no trouble; (2) run the recursion on a thread with a bigger stack — new Thread(() => Dfs(0), maxStackSize: 256 * 1024 * 1024) in C#, ulimit -s or thread attributes in C++; (3) switch to an algorithm whose depth does not grow with the input, such as BFS. Online judges and interview sandboxes rarely let you change the stack size, so (1) is the safe default.

Cycle detection and topological sort

Where DFS clearly beats BFS is cycle detection and topological sorting on directed graphs. The trick is three colours:

• White: not visited yet
• Gray: entered, and still on the current recursion path
• Black: finished; everything reachable from it is done

An edge into a gray vertex points back to an ancestor on the current path, so it closes a cycle. And the order in which vertices turn black (post-order), reversed, is a topological order: a vertex finishes only after everything that must come after it has finished.

Our example is a small build pipeline, where an arrow means "must finish before".

enum Color { WHITE, GRAY, BLACK };   // unvisited / on the current path / finished

bool dfs(int v) {
    color[v] = GRAY;
    for (int w : out[v]) {
        if (color[w] == GRAY) {                // back edge: w is an ancestor of v
            for (int x = v; x != w; x = parent[x]) cycle.push_back(x);
            cycle.push_back(w);
            std::reverse(cycle.begin(), cycle.end());
            return false;
        }
        if (color[w] == WHITE) {
            parent[w] = v;
            if (!dfs(w)) return false;
        }
    }
    color[v] = BLACK;
    post.push_back(v);                         // all dependants are done
    return true;
}
// sort(): call dfs on every WHITE vertex, then print post in reverse

We ran it once on the graph above, then again after adding a mistaken edge package -> deps:

order: checkout codegen deps compile test package
cycle: deps -> compile -> test -> package -> deps

Following the parent links lets you print the actual loop, not just "there is a cycle". That is how build tools and package managers can report "circular dependency: A -> B -> C -> A".

The classic mistake is to skip the gray/black distinction and treat any visited vertex as a cycle. We changed the condition to color[w] != WHITE and ran it again: the acyclic graph was reported as cyclic on the edge compile -> package. All that happened was that package had already finished (via test) when compile looked at it a second time. For undirected graphs "a visited neighbour that is not my parent" works; for directed graphs you need all three colours.

Topological order can also be computed with Kahn's algorithm, which repeatedly removes vertices with in-degree zero using a queue. It is BFS-flavoured and has no recursion-depth risk on huge graphs; DFS is handier when you want to show the offending cycle.

Checking the 2021 code: shortest paths with DFS

We copied both 2021 examples verbatim and compiled them:

• Example 1, matrix DFS: zero warnings with -Wall -Wextra, and the original input produced the original output (visit order 1 2 4 8 5 6 3 7). As in the BFS article, map[30][30] limits vertex numbers to 29.
• Example 2, maze shortest distance with DFS: compiled cleanly and printed the original answer, 13, after 27 DFS calls. It had two real problems.

First, it prints a wrong value for an unreachable goal. It prints the initial min = n * n unchanged, so a 3×3 maze with the middle row blocked printed a shortest distance of 9. You need a sentinel such as -1 to tell "no path" apart.

Second, it enumerates every path, so it is exponential. It is backtracking: the visited mark is undone on the way out (map[y][x] = 1), so the more open the grid, the more paths it explores. Built with clang -O2, on empty n×n grids:

BFS solves the same 7×7 grid by pushing each of its 49 cells once. At 10×10, the size limit of the 2021 code's map[10][10], the DFS version would not finish in any reasonable time. Use BFS for shortest distances; use DFS for "is there a path", "count every combination" and "is there a cycle". Every 2021 diagram (graph, adjacency matrix, maze grids) has been replaced with the new figures and real program output.

When to reach for DFS

Recursive DFS is short and readable, but as soon as the depth can grow with the input, the 100k–170k numbers above become a hard ceiling. Small test inputs will not reveal it, so if your graphs can exceed 100,000 vertices, write the iterative version from the start.