A deep recursive DFS in Python on a 100,000-node path graph will likely…
Options
- Run fine, since Python optimizes deep recursion
- Hit a RecursionError, since the default limit is about 1000 (Correct option)
- Run in O(1) space, using the same stack frame
- Be optimized by tail-call elimination in the interpreter
Answer
Hit RecursionError (default limit ~1000)
Why
Every recursive call adds a frame to the call stack. Python limits the depth to about 1000 frames by default to avoid crashing.
A path of 100,000 nodes needs 100,000 nested calls → RecursionError. Python does not optimize tail calls.
Fix: write it iteratively with your own stack (a list).
def dfs(start):
stack, seen = [start], {start}
while stack:
node = stack.pop()
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)Remember
Deep recursion in Python → convert to a loop with a stack.