DFS, Recursion & Iterative Stacks
Explore deep and avoid recursion limits.
DFS, Recursion & Iterative Stacks is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What DFS Does
DFS dives as deep as it can down one path, then backs up and tries the next. Think of exploring a maze hallway by hallway. 🧭
DFS vs BFS
BFS spreads in rings; DFS plunges deep first. Both visit every reachable node, but in a very different order.
The Recursive Shape
Recursive DFS marks a node visited, then calls itself on each unvisited neighbor. The call stack remembers where to return.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Mark Before Recursing
Set visited as you enter a node, before exploring neighbors. Otherwise cycles send DFS into infinite recursion.
The Recursion Limit Trap
Python caps recursion near 1000 calls. A deep graph triggers a RecursionError, which shows up as a runtime error verdict.
Raise the Limit
One quick fix is to lift the cap with setrecursionlimit. Set it above your worst-case depth before running DFS.
import sys
sys.setrecursionlimit(300000)Go Iterative Instead
The safest fix is an iterative DFS using your own stack. No call depth means no recursion crash, ever.
stack = [start]Pop From the Stack
Each step, pop the top of the stack. Last in, first out keeps DFS diving down the most recent path first.
u = stack.pop()Push the Neighbors
After popping u, push each unvisited neighbor onto the stack. Mark them so they are not pushed again.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)The Full Iterative Loop
Repeat pop and push while the stack holds nodes. When it empties, every reachable node has been visited.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Same Cost as BFS
Like BFS, DFS visits each node and edge once, so it runs in O(n + m). Choose by which order suits the task.
Quick Check
Your recursive DFS crashes on a deep graph. Why?
Recap
You run DFS recursively or with your own stack, mark visited on entry, and switch to iterative when the graph gets deep. 🎉
Frequently asked questions
Is the “DFS, Recursion & Iterative Stacks” lesson free?
Yes — the full text of “DFS, Recursion & Iterative Stacks” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “DFS, Recursion & Iterative Stacks”?
Explore deep and avoid recursion limits. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “DFS, Recursion & Iterative Stacks” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Adjacency Lists from Input
- BFS for Shortest Unweighted Paths
- DFS, Recursion & Iterative Stacks
- Connected Components & Flood Fill