The DFS that died a thousand calls deep

A connected-components counter passes every unit test — small random graphs, stars, cliques. On the first production input, a road network containing one long chain of 100,000 nodes, it dies with RecursionError: maximum recursion depth exceeded. The same algorithm in C++ handles the input fine. A teammate proposes sys.setrecursionlimit(10**9) as the fix. Evaluate that proposal, find the real issue, and fix it properly.

1def count_components(n, adj):
2    visited = [False] * n
3 
4    def dfs(u):
5        visited[u] = True
6        for v in adj[u]:
7            if not visited[v]:
8                dfs(v)
9 
10    comps = 0
11    for u in range(n):
12        if not visited[u]:
13            comps += 1
14            dfs(u)
15    return comps
16 
17 
18n = 100_000
19adj = [[] for _ in range(n)]
20for i in range(n - 1):              # one long path: 0 - 1 - 2 - ... - 99999
21    adj[i].append(i + 1)
22    adj[i + 1].append(i)
23 
24print(count_components(n, adj))     # RecursionError: maximum recursion depth exceeded

1. What is Python's default recursion limit, and how deep does this DFS recurse on a path graph with 100,000 nodes?
2. Why do small random graphs, stars and cliques all pass? What input *shape* triggers the failure?
3. Evaluate sys.setrecursionlimit(10**9): what does the limit actually protect, and what happens when you raise it far beyond the real stack?
4. Rewrite the DFS iteratively with an explicit stack. Where do you mark a node visited, and what goes wrong if you mark on pop instead of on push?
5. Does the iterative version visit nodes in the same order as the recursive one? Does it matter here?
6. State the complexity of the fixed version, including stack memory.